以前の記事「文字列の頭良い感じの線形アルゴリズムたち」で、
この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、
その辺りの説明は他のサイトにお任せします。
と書いたところ、周期性の判定の方に関して「"他のサイト"なんてものはない」と言われてしまったので、書きます。
文字列 S が与えられる。S[0~i] の最小の周期長を全部まとめて O(N) で求めよ。
という問題を考えます。例えば、
abababcaa 122222778
という感じ。（上がSで下が答えの配列）
例えば、"ababa"なら"ab"を繰り返せばいいので 2 という感じ。
解法
KMPでテーブルを作ります。
んで、「i - KMP[i]」が各場所の答え（1-indexed）
簡単な解説
「最小の周期長」＝「k 文字ずらしたものが元の文字列と一致するような最小の k (k>0)」
例えば、"ababa"は
ababa __ababa
2 文字ずらした時に初めて同じ列にある文字同士が一致するので 2 が答え。
この同値関係は この記事 が参考になるかも
で、「k 文字ずらしたものが元の文字列と一致するようなhogehoge」ってKMPそのものみたいなものですよねという。
