Repeat String Query

2 secs 1024 MB
bayashiko's icon bayashiko

KMP法を用いることで全ての連続部分文字列について最小周期を O(S2)O(|S|^2) で求めることが出来ます。 (すぬけさんの記事に詳しく書いてあります)
連続部分文字列の長さ LL が最小周期 cl,rc_{l,r} で割り切れる場合答えは L/cl,rL/c_{l,r} 、割り切れない場合は 11 です。
よって計算量は全体で O(S2+Q)O(|S|^2+Q) です。
なんかロリハでlogつけても高速化すれば通るっぽいです(そ、そんな…)