扩展 KMP（Z 函数）

luckydrawbox · 2022-08-11 23:51:29 · 个人记录

变量

函数

代码

int z[N];
void getz(string s){
    int len=s.size(),l=0;
    z[0]=0;
    for(int i=1;i<len;i++){
        z[i]=0;
        if(l+z[l]>i)
            z[i]=min(l+z[l]-i,z[i-l]);
        while(i+z[i]<len&&s[z[i]]==s[i+z[i]])
            z[i]++;
        if(i+z[i]>l+z[l])
            l=i;
    }
    z[0]=len; 
}