Z 算法 / 扩展 KMP (Z-Algorithm)¶

Z 算法（也称扩展 KMP，ExKMP）用于在 \(\mathcal{O}(n)\) 时间复杂度内计算字符串 \(s\) 的 Z 函数（Z-array）。

算法定义与性质¶

对于长度为 \(n\) 的字符串 \(s\)，定义 \(z[i]\) 为字符串 \(s\) 与其从下标 \(i\) 开始的后缀 \(s[i \dots n-1]\) 的最长公共前缀 (Longest Common Prefix, LCP) 长度：

\[ z[i] = \operatorname{LCP}(s, s[i \dots n-1]) \]

通常约定 \(z[0] = 0\)（在某些定义中记为 \(n\)）。

算法维护一个匹配区间 \([l, r]\)（称为 Z-box），代表当前探测到的右端点 \(r\) 最远的前缀匹配段（即 \(s[l \dots r] == s[0 \dots r - l]\)）。利用已有匹配信息，单次转移均摊 \(\mathcal{O}(1)\)，整体复杂度为严格 \(\mathcal{O}(n)\)。

Z 函数模版¶

#include <vector>
#include <string>
#include <algorithm>

// 计算字符串 s 的 z 数组 (z[0] = 0)
// 时间复杂度: O(n)，空间复杂度: O(n)
std::vector<int> z_function(const std::string &s) {
    int n = s.size();
    std::vector<int> z(n, 0);
    int l = 0, r = 0; // 当前最远匹配区间 [l, r]

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

经典应用¶

1. 模式串匹配 (替代 KMP)¶

给定文本串 \(T\) 与模式串 \(P\)，寻找 \(P\) 在 \(T\) 中的所有出现位置。

构造拼接串：

\[ S = P + \# + T \]

其中 \(\#\) 为未在 \(P\) 和 \(T\) 中出现过的分隔符。对 \(S\) 计算 Z 函数，若对于某个位于 \(T\) 对应的下标 \(i\)，有 \(z[i] == |P|\)，则说明在 \(T\) 中以该位置起始的子串与 \(P\) 完全匹配。

// 在 text 中检索 pattern 的所有匹配起始下标 (0-indexed)
std::vector<int> z_search(const std::string &text, const std::string &pattern) {
    if (pattern.empty() || text.size() < pattern.size()) return {};

    std::string s = pattern + "#" + text;
    std::vector<int> z = z_function(s);

    std::vector<int> matches;
    int p_len = pattern.size();

    for (int i = p_len + 1; i < (int)s.size(); ++i) {
        if (z[i] == p_len) {
            matches.push_back(i - p_len - 1);
        }
    }
    return matches;
}

2. 字符串最小周期¶

对于长度为 \(n\) 的字符串 \(s\)，若存在一个下标 \(i\) 使得 \(i + z[i] == n\) 且 \(n \bmod i == 0\)，则 \(i\) 即为 \(s\) 的一个周期（前缀 \(s[0 \dots i-1]\) 重复多次可得整个字符串）。最小的满足条件的 \(i\) 即为最小周期。

扩展：ExKMP (计算 T 的每个后缀与 P 的 LCP)¶

若不想拼接长字符串，可以直接先对模式串 \(P\) 计算其 \(z\) 数组，再通过双指针递推计算 \(T\) 的各后缀与 \(P\) 的 LCP。

// 返回 vector<int> lcp, 其中 lcp[i] = LCP(P, T[i...|T|-1])
std::vector<int> exkmp(const std::string &T, const std::string &P) {
    int n = T.size(), m = P.size();
    std::vector<int> z = z_function(P);
    std::vector<int> lcp(n, 0);

    int l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        if (i <= r) {
            lcp[i] = std::min(r - i + 1, z[i - l]);
        }
        while (i + lcp[i] < n && lcp[i] < m && P[lcp[i]] == T[i + lcp[i]]) {
            lcp[i]++;
        }
        if (i + lcp[i] - 1 > r) {
            l = i;
            r = i + lcp[i] - 1;
        }
    }
    return lcp;
}

LeetCode 经典真题精选与题解提示¶

LeetCode 2223 - 构造字符串的总得分和 (Sum of Scores of Built Strings) 困难
提示

Z 函数原形定义题。
- 题意定义：得分即为各个后缀与原串的最长公共前缀 (LCP) 之和。
- 对给定字符串 \(s\) 直接计算其 Z 函数数组 \(z\)。最终总得分即为 \(\sum_{i=1}^{n - 1} z[i] + n\)（全串与自身的 LCP 为 \(n\)）。
LeetCode 3031 - 将单词恢复初始状态所需的最少时间 II (Minimum Time to Revert Word to Initial State II) 困难
提示

后缀等于前缀判定 (Z 函数快速校验)。
- 每一步操作相当于截断前 \(k\) 个字符并在末尾补充任意字符。若操作 \(t\) 次，只要原串在下标 \(t \times k\) 起始的后缀是原串的前缀，末尾补充的字符就可以完美还原初始单词。
- 计算原串的 Z 数组。枚举步数 \(t \ge 1\)：若 \(t \times k < n\)，检查是否满足 \(z[t \times k] == n - t \times k\)；一旦满足立即返回 \(t\)。若枚举完毕仍无匹配，则返回 \(\lceil n / k \rceil\)。
LeetCode 3045 - 统计前后缀下标对 II (Count Prefix and Suffix Pairs II) 困难
提示

Z 函数 / 前后缀校验 + 字典树 (Trie)。
- 字符串 \(s_1\) 是 \(s_2\) 的前后缀下标对，当且仅当 \(s_1\) 同时为 \(s_2\) 的前缀与后缀。
- 结合 Z 数组快速判定：对每个单词 \(w\)，其长度为 \(L\) 的前缀同时是后缀的充要条件为 \(z[|w| - L] == L\)。
- 亦可将每个字符串的双端字符对 \((w[i], w[|w| - 1 - i])\) 作为字典树的单个节点构建复合 Trie，边插入边统计前缀计数。