z-algorithm メモ

vector<int> Zalgo(string &s)
{
int n = (int)s.size();
vector<int> res(n , 0);
res[0] = 0;
int j=1;//最も右まで調べたときの左端の値
for (int i = 1; i <= n; ++i){
if(j+res[j]<=i){//未到達の場所に来た
res[i]=0;
}else{
res[i]=min(res[j]-i+j,res[i-j]);
}
/*
if(res[j]+j<i+res[i-j]) res[i]=res[j]-(i-j);
//iからres[i-j]だけ伸ばしたとき、調べてる最も右(j+res[j])をはみ出る
else res[j+(i-j)]=res[0+i-j];
//はみ出ないのでそのまま 0-res[j]とj-j+res[j]は一致なので
res[j]+j<i+res[i-j]⇔res[j]-(i-j)<res[i-j]よりminで書ける
*/
while(i+res[i]<n && s[i+res[i]]==s[res[i]]){
++res[i];
}
if(j+res[j]<i+res[i])j=i;
}
res[0]=n;
return res;
}