Suffix Array まとめ

画像

Suffix Arrayとは

文字列$S$で、各位置$i$から末尾までの文字列を昇順ソートしたもの。
これによって、構築は$O(NlogN^2)$かかるが、文字列検索を$O(MlogN)$で行える。

LCPとは

文字列S中で隣り合う文字列の最大共通接頭辞を求める配列のこと
文字列Sの昇順を求めて、それの隣り合う最大長を求めて、それを使って尺取法をする。

Suffix Array+LCP+セグメント木で簡単に任意の範囲の最小値が取れるので嬉しい。

最後に

今度丁寧に書きたい