Z 函数
2026-08-05
下文约定下标从 1 开始。
定义
对于一个字符串 s,我们定义 Z 函数 z[i] 表示 s 与 s[i∼n] 的最长公共前缀(LCP)的长度:
z[i]=LCP(s[1∼n],s[i∼n])
特别的,规定 z[1]=0。
流程
下文介绍一个 O(n) 计算 z 数组的算法。
对于 i(2≤i≤n),我们称区间 [i,i+z[i]−1] 为匹配段(Z-Box),显然,[1,z[i]−1] 与 [i,i+z[i]−1] 对应字串相同。
接下来我们维护最右侧的匹配段 [l,r],根据定义,字串 s[l∼r] 是 s 的一个前缀。
初始时,令 l=1,r=0,接下来,我们依次更新 i∈[2,n] 的 z[i]:
- 若 i>r,此时暴力更新计算 z[i]。
- 若 i≤r,此时根据定义,有 s[l∼r]=s[1∼r−l+1],此时,我们令 i 在 [1,r−l+1] 中的对应位置为 j=r−i+1,显然有 z[i]≥min(z[j],r−i+1),现在根据 z[j] 与 r−i+1 的关系进行讨论:
- 若 z[j]>r−i+1,即 j 的匹配放到 i 上出了边界 r,我们需要令 z[i]←r−i+1,然后暴力更新。
- 若 z[j]≤r−i+1,即 j 的匹配右界不超过 r,直接令 z[i]←z[j] 即可。
别忘了更新 l,r。
