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