文字列sの各prefixに対して、そのprefixとsuffixが一致する最大の長さをO(|s|)で取得する
できること
各prefixについて、その最小周期を求める
substr(0,i)の最小周期はi-res[i]とかける
証明
string sの先頭r文字と末尾r文字が一致するとき(⇔substr(0,r)==substr(i-r,r))
・i-r<=rのとき（先頭r文字と末尾r文字が重なる）
r文字のprefix,suffixが等しいことから、
substr(0,i-r)==substr(i-r,i-r),substr(i-r,i-r)==substr(i-r+r,i-r),...
これより、substr(0,i-r)==substr(i-r,i-r)==substr(i-r+r,i-r)...が得られるが、これはsがi-r文字の周期を持つことを表す
(iがrの倍数でない場合末尾の表記が面倒なので省略、いずれにせよ周期性は示せる）
・r<i-rのとき（先頭r文字と末尾r文字が重ならない）
s=substr(0,i-r)+substr(i-r,r)であり、先頭r文字と末尾r文字の一致から、sは明らかにi-r文字の周期を持つ
逆にsが周期Tを持つとき、一周期に対応する文字列をt、tのprefixをt'として、s=t+t+t+...+t+t' が成り立つ。
これはsの中に存在する任意の周期に対して成り立つので、tをsの最小周期としてよい。
このとき、sから末尾t文字を除いた文字列と、sから先頭t文字を除いた文字列は一致するので、r=i-t⇔t=i-rと書ける。
文字列sの中にある文字列tをO(|s|)で検索（s中のtの開始位置の列挙）する
aを先頭から見て、bと照合していくことを考える
bに関してresテーブルを構築しておく
a[i,i+x-1]とb[0,x-1]が一致していて、a[i+x]とb[x]が異なるとき、a[i+i-res[x],res[x]]とb[0,res[x]]が一致しているので、res[x]>0である限り、次に a[i+x]とb[res[x]]を比較すればよい
aは各文字につき一回しか見ない、なおかつxは高々|s|回しか増えない→while中で高々|s|回しか減らないので、O(|s|)で検索ができる
verify
https://codeforces.com/gym/102465/problem/K