Suffix Array（接尾辞配列）とLCP（最長共通接頭辞）arrayを線形時間で構築する方法を調べてみた 〜SA-ISとKasai's algorithm〜 - naoya_t@hatenablog

suffix arrayは知ってます。（当然） （知ったきっかけは何だったかな…高林さんのsaryかな） 以前、英辞書検索用のCLIツールを作る時などにも使いました。 でも今までずっと、文字列のポインタを1つずつずらした（文字列の長さ分の）char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な（の）書き方しかしたことがありませんでした。 あまりそれで困るような場面に遭遇したことがなかったということでもありますが、 競プロで使うとなるとそういうわけにはいきません。 制約がとかだともう無理ですよね。 LCP（最長共通プレフィックス）array もそうです。 suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。 隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックス