読者です 読者をやめる 読者になる 読者になる

文字列の周期性判定

以前の記事「文字列の頭良い感じの線形アルゴリズムたち」で、

この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、
その辺りの説明は他のサイトにお任せします。

と書いたところ、「"他のサイト"なんてものはない」と言われてしまったので、書きます。

文字列 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そのものみたいなものですよねという。

練習問題