Suffix Array の効率は考慮していない

• ref:http://asip.tdiary.net/20070621.html#p04
• ref:http://4topcoder.blogspot.com/2007/03/suffix-array_27.html

ASIPさんが「効率をある程度考慮した Suffix Array」としてクリップしているようですが、これ、誤解しているんじゃないだろうか。
件のページの Suffix Array 構築はもっともナイーブなもので、自分が書いたものと基本的に同じだ。ただ、比較の度に substring をコールしたりしないのでその分高速ではある。
が、件のページの肝は Suffix Array により任意部分文字列が二分探索で検索でき、 contains を使った検索よりはるかに高速になるという話であって、Suffix Array 自身のコードは特に効率を気にしたものにはなっていない。ただ、高々 2,500 文字程度だからナイーブなアルゴリズムで多少構築コストが高くても十分実用的だというだけの話。