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;
}

拓展

给定两个字符串 $S,T$，长度分别为 $n,m$。对于每个 $1\le i\le n$，求出 $p_i=\text{lcp}(S_{[i,n]},T)$。

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

基本是一样的，先求出 $T$ 的 $z$ 数组，若存在 $j$ 满足 $j<i$ 且 $j+p_j-1\ge i$，则 $p_i$ 至少为 $\min(z_{i-j+1},j+p_j-i)$。那么记录 $r+p_r-1$ 最大的 $r$ 即可，时间复杂度还是线性的。

例题：P5410 【模板】扩展 KMP/exKMP（Z 函数）