第 85 课·字符串算法高级

Z 算法

z-algorithmz-arraypatternmatch

第85课 - Z算法

学习目标

通过本节课的学习，你将能够：

  1. 理解Z数组的定义、性质及其在字符串处理中的强大作用。
  2. 掌握构造Z数组的线性时间复杂度算法的核心思想与流程。
  3. 能够应用Z算法高效地解决经典的字符串模式匹配问题。
  4. 分析Z算法的时间与空间复杂度。
  5. 将Z算法与上一课的Manacher算法及其他字符串算法进行对比。

核心概念

什么是Z数组？

想象一下，对于一个字符串 S，我们想知道从每个位置 i 开始的子串，与字符串的前缀 S[0..n-1] 最长的相等长度是多少。Z数组就是用来存储这个信息的。

定义：给定一个长度为 n 的字符串 S，其Z数组 Z[0..n-1] 是一个长度为 n 的数组，其中 Z[i] 表示子串 S[i..n-1] 与字符串 S 本身最长公共前缀的长度。

  • 约定 Z[0] = 0（因为一个字符串的前缀通常不包括它自身，但在实现中有时设为 n 或按需处理）。
  • 对于 i > 0，Z[i] 是满足 S[0...k-1] == S[i...i+k-1] 的最大的 k。

通俗比喻：Z数组就像一把“秘密回文子串”的尺子，但这里比较的是和开头的相似程度，而不是中心对称。Z[i] 告诉你，从位置 i 开始的字符串，和原字符串的开头（前缀）能“匹配”多远。

Z算法：高效构造Z数组的引擎

暴力计算Z数组需要 O(n²) 的时间。Z算法通过维护一个“窗口”[L, R]（表示已知的、与前缀匹配的、最靠右的子串），并利用已计算的Z值信息，实现了 O(n) 的线性时间复杂度。

核心思想：当计算 Z[i] 时，如果 i 位于当前窗口 [L, R] 内部，我们可以利用 Z[i-L] 的值来跳过一些比较。这是算法高效的关键。

算法流程：

  1. 初始化一个窗口 [L, R]，开始时 L = 0, R = 0。
  2. 从 i = 1 开始遍历到 n-1。
  3. 情况A：i > R
    • 说明 i 在已知窗口之外，需要从头开始朴素匹配。
    • 令 L = R = i，然后逐步增加 R 直到 S[R] != S[R-L]。
    • Z[i] = R - L，并更新 R = R - 1。
  4. 情况B：i <= R
    • i 在窗口 [L, R] 内部。设 k = i - L。
    • 如果 Z[k] < R - i + 1，说明 S[i..] 与 S[0..] 的匹配长度完全包含在窗口 [L, R] 内，因此 Z[i] = Z[k]。
    • 否则（Z[k] >= R - i + 1），我们只能确定 Z[i] 至少为 R - i + 1。然后从 R+1 处开始朴素比较，尝试扩展窗口。
    • 更新 L = i，并根据新的匹配结果更新 R 和 Z[i]。

下面这个流程图清晰地展示了这个逻辑：

flowchart TD
    A[开始: 初始化 L=0, R=0] --> B{i=1 到 n-1};
    B --> C{i > R?};
    C -- 是 --> D[从头朴素匹配<br>设 L=R=i, 扩展 R 直到失配<br>Z[i]=R-L, R=R-1];
    C -- 否 --> E[设 k=i-L];
    E --> F{Z[k] < R-i+1?};
    F -- 是 --> G[Z[i] = Z[k]];
    F -- 否 --> H[从 R+1 开始朴素匹配<br>扩展 R, 更新 Z[i] 和窗口];
    D --> B;
    G --> B;
    H --> B;
    B -- 循环结束 --> I[返回 Z 数组];

Z算法的应用：模式匹配

一个直接的应用是字符串匹配。给定文本串 T 和模式串 P，我们构造一个新字符串 S = P + '$' + T（$ 是一个不在 T 和 P 中的特殊字符）。然后计算 S 的Z数组。

  • 遍历Z数组，当 Z[i] 的长度等于 P 的长度时，就说明在文本串 T 的 i - |P| - 1 位置找到了一个匹配。

代码示例

下面是一个用 Python 实现的 Z算法，以及一个使用它进行模式匹配的示例。

def build_z_array(s):
    """
    构造字符串 s 的 Z 数组。
    参数:
        s (str): 输入字符串
    返回:
        list[int]: Z 数组，z[0] 被设为 0（或字符串长度，根据约定）
    """
    n = len(s)
    if n == 0:
        return []
    
    z = [0] * n
    # 初始窗口 [l, r]
    l, r = 0, 0
    
    # 从 i=1 开始计算
    for i in range(1, n):
        # 情况 B: i 在窗口内
        if i <= r:
            k = i - l
            # 利用 Z[k] 的值，但要受到窗口右边界 R 的限制
            z[i] = min(r - i + 1, z[k])
        
        # 情况 A (i > r) 或 情况 B 的扩展部分：朴素比较，尝试从当前位置 i+z[i] 开始匹配
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        
        # 如果匹配延伸超过了当前窗口，则更新窗口
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    
    # 根据常见约定，将 z[0] 设置为字符串长度（表示整个字符串是其前缀）
    z[0] = n
    return z

def z_search(text, pattern):
    """
    使用 Z 算法在 text 中搜索 pattern 的所有出现位置。
    参数:
        text (str): 文本串
        pattern (str): 模式串
    返回:
        list[int]: 模式串在文本串中出现的所有起始索引列表
    """
    if not pattern:
        return []
    if len(pattern) > len(text):
        return []
    
    # 构造新字符串 S = pattern + '$' + text
    concat = pattern + '$' + text
    z = build_z_array(concat)
    
    pattern_len = len(pattern)
    matches = []
    
    # 遍历 z 数组中与 text 对应的部分（从 pattern_len+1 开始）
    for i in range(pattern_len + 1, len(concat)):
        # 如果 z[i] 的长度等于模式串长度，说明找到一个匹配
        if z[i] == pattern_len:
            # 转换回在原始 text 中的索引: i - (pattern_len + 1)
            matches.append(i - pattern_len - 1)
    
    return matches

# 示例使用
if __name__ == "__main__":
    # 示例1：构建 Z 数组
    s = "aabaabc"
    z_array = build_z_array(s)
    print(f"字符串: '{s}'")
    print(f"Z 数组: {z_array}")
    # 预期输出: Z数组类似 [7, 1, 0, 3, 1, 0, 0] (z[0]=7 表示整个字符串)
    
    # 示例2：模式匹配
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    positions = z_search(text, pattern)
    print(f"\n在文本 '{text}' 中搜索模式 '{pattern}'")
    print(f"找到的位置: {positions}")
    # 预期输出: 位置 [9]

代码输出解释：

  • 对于字符串 "aabaabc"：
    • Z[0] = 7 (整个字符串匹配)
    • Z[1] = 1 ("a" 匹配第一个字符 'a')
    • Z[2] = 0 ("a" 与 'a' 匹配？不，S[2]='b' 与 S[0]='a' 不匹配)
    • Z[3] = 3 ("abc" 与 "aab" 不匹配？等等，S[3]='a', S[4]='b', S[5]='c' 和 S[0]='a', S[1]='a', S[2]='b' 比较，前两个字符 'a','b' 匹配，第三个 'c' 与 'b' 不匹配。所以 Z[3] 应该是2？让我们再检查一下算法逻辑或例子。注意：一个常见的容易出错的例子是 aabca，其Z数组是 [5,1,0,0,1]。对于 "aabaabc"，正确的Z数组应该是 [7, 1, 0, 3, 1, 0, 0]。Z[3]=3 是因为 S[3..] = "abc" 与 S[0..] = "aabaabc"，比较 S[0]='a' vs S[3]='a'，S[1]='a' vs S[4]='b'（不匹配！），所以只匹配了1个字符？这里似乎有矛盾。让我们重新审视字符串 "aabaabc" 和Z数组的计算。

正确的Z数组计算： 字符串: a a b a a b c (索引 0-6)

  • Z[0]: 设为7 (整个字符串)
  • Z[1]: s[1..] = "abaabc"，与s[0..]比较：s[0]='a', s[1]='a' -> 匹配；s[1]='a', s[2]='b' -> 不匹配。所以Z[1]=1。
  • Z[2]: s[2..] = "baabc"，与s[0..]比较：s[0]='a', s[2]='b' -> 不匹配。所以Z[2]=0。
  • Z[3]: s[3..] = "aabc"，与s[0..]比较：s[0]='a', s[3]='a' -> 匹配；s[1]='a', s[4]='a' -> 匹配；s[2]='b', s[5]='b' -> 匹配；s[3]='a', s[6]='c' -> 不匹配。所以匹配了3个字符，Z[3]=3。
  • Z[4]: s[4..] = "abc"，与s[0..]比较：s[0]='a', s[4]='a' -> 匹配；s[1]='a', s[5]='b' -> 不匹配。所以Z[4]=1。
  • Z[5]: s[5..] = "bc"，与s[0..]比较：s[0]='a', s[5]='b' -> 不匹配。所以Z[5]=0。
  • Z[6]: s[6..] = "c"，与s[0..]比较：s[0]='a', s[6]='c' -> 不匹配。所以Z[6]=0。

所以正确的Z数组是 [7, 1, 0, 3, 1, 0, 0]。Z[3]=3 是因为从索引3开始的子串 "aabc" 和字符串开头 "aab" 的前3个字符 a,a,b 是匹配的（注意：S[0..2]="aab", S[3..5]="aab"）。是的，S[3]='a', S[4]='a', S[5]='b' 确实与 S[0]='a', S[1]='a', S[2]='b' 匹配。之前我的快速检查有误。

因此，代码示例中的输出是符合逻辑的。

实践练习

  1. 基础应用：给定字符串 S = "abcabcabcabc"，请手动计算或通过代码得到其Z数组。观察数组中有哪些有趣的规律？这与字符串的周期性有什么关系？

    • 要求：写出Z数组的结果。
    • 预期输出示例：[12, 0, 0, 9, 0, 0, 6, 0, 0, 3, 0, 0] (请验证)

  2. 算法变体：原代码中 build_z_array 函数将 z[0] 设为了 n。请修改函数，使其遵循更“标准”的约定：z[0] 设为 0。同时，思考一下，在应用Z算法进行模式匹配时，这种改变会影响最终结果吗？为什么？

    • 要求：提供修改后的函数代码片段，并回答思考题。

  3. 进阶挑战：使用Z算法解决一个“找到字符串中所有出现的周期”问题。对于一个字符串，如果存在一个子串 P 使得 S 可以由 P 重复多次构成，那么 P 就是 S 的一个周期。例如，"ababab" 的周期是 "ab" 和 "abab"。请编写一个函数，利用Z数组找出给定字符串的所有可能的“最小周期”长度。

    • 要求：编写函数 find_periods(s)，返回一个包含所有最小周期长度的列表。
    • 输入：s = "ababab"
    • 预期输出：[2, 4] （因为 "ab" 和 "abab" 都是周期，且它们是最小的）

常见

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「位运算基础」 以巩固所学知识。