Z 算法(EX KMP)学习笔记

给定长 nn 的字符串 SS,对于每个 1in1\le i\le n,求出 ziz_i 表示 lcp(S,S[i,n])\text{lcp}(S,S_{[i,n]})

时间复杂度 O(n)O(n)

类似 manacher,若存在 jj 满足 j<ij<ij+zj1ij+z_j-1\ge i,则 ziz_i 至少为 min(zij+1,j+zji)\min(z_{i-j+1},j+z_j-i)

那么记录 p+zp1p+z_p-1 最大的 pp,每次暴力拓展 ziz_i 都会令 p+zp1p+z_p-1 增加 11,所以时间复杂度均摊 O(n)O(n)

注意 z1z_1 要单独计算。

代码如下:

z[1]=n;
for(int i=2,rb=2;i<=n;i++)
{
    if(rb+z[rb]-1>=i) z[i]=min(z[i-rb+1],rb+z[rb]-i);
    while(z[i]<n-i+1&&a[z[i]+1]==a[i+z[i]]) z[i]++;
    if(i+z[i]>rb+z[rb]) rb=i;
}

练习题目: