Suffix Array（接尾辞配列）とLCP（最長共通接頭辞）arrayを線形時間で構築する方法を調べてみた 〜SA-ISとKasai's algorithm〜
suffix arrayは知ってます。（当然）
（知ったきっかけは何だったかな…高林さんのsaryかな）
以前、英辞書検索用のCLIツールを作る時などにも使いました。
でも今までずっと、文字列のポインタを1つずつずらした（文字列の長さ分の）char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な（の）書き方しかしたことがありませんでした。
あまりそれで困るような場面に遭遇したことがなかったということでもありますが、
競プロで使うとなるとそういうわけにはいきません。
制約がとかだともう無理ですよね。
LCP（最長共通プレフィックス）array もそうです。
suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。
隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックスが求められたりして便利（らしい）です。
（配列の長さ-1）組の文字列の比較なので普通に考えたらかかります…よね*1。
なのに、なのにいかにもsuffix arrayとLCP（最長共通プレフィックス）arrayを計算して下さいと言わんばかりの問題*2が来て、上位陣はsuffix arrayで通しているというのです。
そこで
- O(N)でsuffix arrayが構築できる方法
と
- O(N)でLCP arrayが構築できる方法
について調べてみました。
上級者の皆様には「そんな事も知らなかったのか」「蟻本（上級編）に書いてあるぞ」「蟻本読め」「蟻本」と思われることでしょうが青コーダーレベルだと今までそれで困る場面がなかったということでお許しください。
Suffix Array
2009年に出てきたSA-ISというのが現在最強らしいです。
蟻本にも名前は出てきます。(p.337)
なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。例えば、SA-ISと呼ばれるアルゴリズムなど、線形時間で非常に高速に構成するアルゴリズム等も存在していますが、プログラミングコンテストではほとんどの場合で上のアルゴリズム*3で十分です。
SA-IS
論文にCで書かれたコードが載ってます（そのまま動きます）。
仕組みについては日本語で書かれた解説記事があります。
めちゃ賢いアルゴリズムです。
- SA-IS - (iwi) ｛ 反省します - TopCoder部*4
- SA-IS - Shogo Computing Laboratory
- SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei
- SA-IS 法のメモ - まめめも (Rubyで書いてある)
これを使うとSPOJのSARRAYで満点が取れるらしいです。（※まだ試してない）
実装は元論文に載っているCで書かれたコードがそのまま動きます*5。
秋葉さんの記事でおすすめのYuta Moriさんによる実装などもあります。
LCP array
笠井先生が考案した Kasai's algorithm というのがあって、で求めることができるのです。
なんということでしょう！
（※蟻本のpp.339-340にもあります。いかに蟻本を斜め読みしかしていないかが分かります。）
Kasai's algorithm
- Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications (Kasai et al. (2001))
- 文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog; (Java)
- Algorithms with Python / 接尾辞配列 (suffix array) (←詳しい; Python)
LCPが1以上の2つのサフィックスがあるときに、それぞれの2文字目以降のサフィックス同士のLCPは元の2つのサフィックスのLCPより1つ小さい
という事実を使って計算量を節約することができるというアイデアです。
で、それを最大限にやりたいので長い順に（＝元の文字列の先頭から）見ていくことで、でLCP arrayが構築できてしまいます。
