はじめての Suffix Array

死ぬ前に Suffix Array を一度は作ってみようと思っていたが、作ったら死んでしまった。

配列解析の授業のレポートなのだが、なんだろう、この鬼のようなめんどくささは。実装したのは Ko&Aluru。確かにさらっと書いてあるんだけど、O(n) にするためには bucket ソートを駆使しながら、ごねごね配列をいじくり回さないといけない。2-3 木とか簡単だったな。どうしてこうもアルゴリズムの教科書に載ってないのかと思っていたが、こりゃきつい。アルゴリズムも全然自明じゃないし。論文に擬似コードが載ってないのはどしてだろうと思ったが、なるほど、擬似コードを載せても何の理解の助けにもならないからか。

うーん、はなしを聞く限りこれで入り口なんだよなぁ。定数時間で検索したり、圧縮したり、ビット演算使ったりとかいってたよなぁ。うーん、うーん。