Z 算法（EX KMP）学习笔记

给定长 $n$ 的字符串 $S$，对于每个 $1\le i\le n$，求出 $z_i$ 表示 $\text{lcp}(S,S_{[i,n]})$。

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

类似 manacher，若存在 $j$ 满足 $j<i$ 且 $j+z_j-1\ge i$，则 $z_i$ 至少为 $\min(z_{i-j+1},j+z_j-i)$：

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

注意 $z_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;
}
复制代码

练习题目：

• P5410 【模板】扩展 KMP/exKMP（Z 函数）