SRM401 Div2 1000

とぷこだ 過去問

問題

ある電光掲示板があり、それはメッセージを繰り返し表示し続けている。そこで、そのメッセージの長さを調べたい。このメッセージを書きとめた文字列配列runningが与えられる。たとえば"abcabcabcab"であれば、"bca"や"abcabc"というメッセージがありえる。
この可能なメッセージの中で最短のメッセージの長さを返す。

考え方

KMP法のテーブルを使う。
このテーブルは文字列検索以外にも使え、その一つに文字列の周期を調べるのに使える。
(ちょっと理解できてるか怪しいけど、)
spaghetti source( http://www.prefield.com/algorithm/string/knuth_morris_pratt.html )を参考にすると、
fail[n]はn+1文字目で違った場合に戻る場所を表すので、n-fail[n]は最小の文字列の周期を表す。
このテーブルはオートマトンとして考えられるので、それをイメージすればよさそう。