suffix array の検索

ただしくは、検索対象のシーケンスの長さを m として、ナイーブな実装では最悪時間計算量は O(m log n)。Longest Common Prefix(LCP) を計算しておいて、さらに LCP を対象として Range Minimum Query(RMQ) の前準備をしておけば、O(m + log n)。

http://d.hatena.ne.jp/odz/20071204/1196781954

確かに。ちなみに任意の区間での RMQ の準備をしなくても O(m + log n) は可能である。詳しくは suffix array の元論文参照。検索対象のシーケンスと区間の端head, tail それぞれとの longest common prefix の長さを保持しつつ二分探索を行うようにするのだが、その際に区間の端に対応する文字列間の longest common prefix の長さを求めることになる。ここで、実はこの区間の端の取り方が O(n) 通りしかないので単純に全部記録しておいてもよい、ということである。

更に色々情報を加えればO(m)でできるようだけど、これはもはや suffix tree でしょっ？って感じがしないでもない。