Z 函数

~~似乎比 KMP 好理解~~

定义

定义 \(z(i)\) 为 \(s\) 和 \(s(i, n-1)\) 的最长公共前缀长度，定义 \(i\) 的匹配段为 \([l, r]\)。

暴力算法

对于每一个 \(i\)，暴力枚举后面的字符，时间复杂度 \(O(n^2)\)。

代码

for (int i = 0; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
        ++z[i];

线性算法

虽然 \(z(0)\) 显然等于 \(n\)，但我们先令其为 \(0\)。

我们从 \(1\) 开始枚举 \(i\) 计算 \(z(i)\)（原因在下文解释）。令匹配段 \([l, r]\) 为 \(0 \sim i-1\) 中 \(r\) 最大的匹配段。根据定义 \(s(0, r - l) = s(l, r)\)。

若 \(i \leq r\)，那么有 \(s(i, r) = s(i - l, r - l)\) 且 \(s_{i + z(i - l)} = s_{i - l + z(i - l)} = s_{z(i - l)}\)。
- 若 \(z(i - l) < r - i + 1\)，根据 \(z\) 函数的定义，\(s_{i - l + z(i - l) + 1} = s_{i + z(i - l) + 1} \ne s_{z(i - l) + 1}\)，因此 \(z(i) = z(i - l)\)。
- 若 \(z(i - l) \geq r - i + 1\)，也就是说，\(s(i, r)\) 是 \(s\) 的一个前缀，但不一定是最长前缀，此时我们令 \(z(i) = r - i + 1\) 并暴力地更新 \(z(i)\)。
若 \(i > r\)，直接暴力算 \(z(i)\)。

代码

for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1)
        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];
        l = i, r = i + z[i] - 1;
    }
}
z[0] = n;

在实现时，可以发现第一种情况的第二类可以和第二种情况合并，且 \(l\) 和 \(r\) 的更新一定会发生在暴力更新后。

\(i\) 不能从 \(0\) 开始枚举，因为 \(z(0) = n\)，如果 \(i\) 从 \(0\) 开始，那么第一次循环后 \(l = 0, r = n - 1\)。我们使用匹配段是为了用已匹配的字串更新当前 \(z\) 函数值，而 \([0, n - 1]\) 这个匹配段就是原串，因此会使后面所有的 \(z(i) = 0\)。

时间复杂度证明

对于内层循环，因为一定会使 \(r\) 增加，因此最多执行 \(n\) 次；对于外层循环，只会遍历字符串一次。因此时间复杂度 \(O(n)\)。

应用

子串匹配

给定两个字符串 \(a, b\)，求 \(a\) 在 \(b\) 中所有出现的位置。

构造一个字符串 \(s = a + \texttt{#} + b\)，其中 \(\texttt{#}\) 是一个 \(a\) 和 \(b\) 中都没有的字符。求出 \(s\) 的 \(z\) 函数。接下来从 \(i = |a| + 1\) 开始枚举，若 \(z(i) = |a|\)，说明 \(a\) 在 \(b\) 的 \(i - |a| - 1\) 处出现了。时间复杂度 \(O(|a| + |b|)\)，空间复杂度 \(O(|a| + |b|)\)。

周期

最小周期 1

给定一个字符串 \(s\)，求 \(s\) 的最小周期，最后一个周期可以不完整。

我们从 \(1\) 开始枚举 \(i\)，根据 \(z(i)\) 的定义有 \(s(0, z(i) - 1) = s(n - z(i), n - 1)\)，若 \(i + z(i) = n\)，那么 \(s(0, n - i - 1) = s(i, n - 1)\)，根据简介中的结论，\(i\) 是 \(s\) 的一个周期。因为 \(i\) 从小到大枚举，因此找到的第一个周期即为最小周期。

最小周期 2

给定一个字符串 \(s\)，求 \(s\) 的最小周期，最后一个周期必须完整。

此时，最小周期一定是 \(n\) 的因数。因此，只判断 \(n\) 的因数符不符合 \(i + z(i) = n\) 即可。