Z Algorithm

2huk · 2025-06-02 10:48:46 · 算法·理论

默认字符串为 s，长度为 n，从 0 下标。s[l, r] 表示 s 中下标在 l \sim r 的字串。

扩展 KMP 算法需要解决这样的问题：求出一个数组 z_i，表示 s[i,n-1] 和 s 的最长公共前缀长度。

不难发现这个算法解决的问题与 KMP 算法看上去是相似的（KMP 是从 i 往前找，与 s 匹配的最长前缀；而扩展 KMP 是往后找），尽管两者的解决方法完全不同。

显然可以通过二分+哈希在 \mathcal O(n \log n) 的复杂度内轻松解决，但其并没有正确性保障，且复杂度偏高。而扩展 KMP 可以在线性时间复杂度内解决这个问题，且代码复杂度并不复杂许多。

接下来介绍这个算法的流程。

我们按照从前往后的顺序递推地求出 z_i，即我们默认 z_0 \dots z_{i-1} 均已求解。

根据定义，s[0,z_i-1] 和 s[i,i+z_i-1] 是相同的。令 j \in [0,i-1] 中最大的 j+z_j-1 为 r，这个 j 为 l。那么 s[l,r] = s[0,r-l]。初始 l=r=0。

此时显然有 l \le i。我们讨论 i 与 r 的关系。

下图中相同颜色的线段所代表的子段是相同的。原因请分别思考。

•  显然 $s[i-l,r-l]=s[i,r]$。此时考察 $z_{i-l}$。进行分类讨论： - $i + z_{i-l} \le r$，即：  显然 $s_{z_{i-l}} \ne s_{i-l+z_{i-l}}$（$z_{i-l}$ 的定义）。而 $s_{i-l+z_{i-l}} = s_{i+z_{i-l}+1}$（都在红色线段内），所以 $s_{z_{i-l}} \ne s_{i+z_{i-l}+1}$。所以 $z_i = z_{i-l}$。 - $i+z_{i-l}>r$，即：  此时我们无法保证 $s_{i-l+z_{i-l}} = s_{i+z_{i-l}+1}$，所以没有快速递推的方法。但是显然 $z_i \ge r-i+1$，于是直接令 $z_i = r-i+1$，然后暴力枚举下一个字符扩展直到 $z_i$ 不能扩展为止。 $z_i \ge r-i+1$ 意味着 $i + z_i-1 \ge r$，也就是 $r$ 一定会增大。而 $r$ 最大为 $n-1$，所以这里的暴力平摊是 $\mathcal O(1)$ 的。

代码直接写会很丑陋：

for (int i = 0, l = 0, r = 0; i < n; ++ i ) {
    if (i <= r) {
        if (i + z[i - l] <= r) {
            z[i] = z[i - l];
        } else {
            z[i] = r - i + 1;
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++ ;
        }
    } else {
        z[i] = 0;
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++ ;
    }
    if (i + z[i] - 1 > r) {
        l = i, r = i + z[i] - 1;
    }
}

优化后：

for (int i = 0, l = 0, r = 0; i < n; ++ i ) {
    if (i + z[i - l] <= r) {
        z[i] = z[i - l];
    } else {
        z[i] = max(0, r - i + 1);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++ ;
    }
    if (i + z[i] - 1 > r) {
        l = i, r = i + z[i] - 1;
    }
}