MP法 メモ

文字列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