Z算法（线性时间模式匹配）

数据结构与算法专题 · Z函数与字符串匹配的统一框架

专题：数据结构与算法系统学习

关键词：数据结构, 算法, Z算法, Z函数, Z数组, 字符串匹配, 线性时间, 字符串周期, KMP对比

一、概述

Z算法（Z Algorithm），也称Z函数（Z-function），是一种用于字符串处理的线性时间算法。它通过计算一个称为"Z数组"的辅助数组，能够在 O(n + m) 时间内高效解决字符串匹配问题。Z算法的核心思想是从每个位置出发，计算该位置的后缀与字符串前缀的最长公共长度（LCP），并利用已经计算过的区间信息进行跳跃式推进，从而避免重复比较。

Z算法与著名的KMP算法（Knuth-Morris-Pratt）在本质上是等价的——它们都利用字符串的"自相似性"来加速匹配过程，只是从不同的角度切入。KMP通过前缀函数（π函数）实现，而Z算法通过Z函数实现。理解Z算法不仅能掌握另一种线性时间字符串匹配方法，还能加深对字符串周期、前缀函数等概念的全局认识。

核心特性：

时间复杂度：O(n) 计算Z数组，O(n + m) 完成字符串匹配
空间复杂度：O(n) 存储Z数组
核心思想：利用已匹配的区间信息跳过不必要的字符比较
应用范围：字符串匹配、字符串周期、最短前缀、字符串压缩等

二、Z函数与Z数组的定义

给定一个长度为 n 的字符串 s，Z函数（Z数组）是一个长度为 n 的数组，记为 Z[0..n-1]。对于每个位置 i (i > 0)，Z[i] 定义为从位置 i 开始的子串 s[i..n-1] 与整个字符串 s 的最长公共前缀（LCP）的长度。约定 Z[0] = 0（或 n，取决于具体实现习惯，但 Z[0] 在计算中通常不被使用）。

Z[i] = LCP( s, s[i:] ) = max{ k ≥ 0 | s[0..k-1] = s[i..i+k-1] }

示例说明

以字符串 s = "aaabaaab" 为例，手动计算其Z数组：

i = 0：Z[0] = 0（约定，不计自身）
i = 1：s[1..] = "aabaaab"，与前缀 "aaabaaab" 比较，最长公共前缀为 "aa"，所以 Z[1] = 2
i = 2：s[2..] = "abaaab"，与前缀比较，最长公共前缀为 "a"，所以 Z[2] = 1
i = 3：s[3..] = "baaab"，与前缀比较，无匹配，所以 Z[3] = 0
i = 4：s[4..] = "aaab"，与前缀 "aaabaaab" 比较，最长公共前缀为 "aaab"，所以 Z[4] = 4
i = 5：s[5..] = "aab"，最长公共前缀为 "aa"，Z[5] = 2
i = 6：s[6..] = "ab"，最长公共前缀为 "a"，Z[6] = 1
i = 7：s[7..] = "b"，无匹配，Z[7] = 0

最终Z数组为：Z = [0, 2, 1, 0, 4, 2, 1, 0]。观察可以发现，Z[4] = 4 说明从位置4开始，有一个长度为4的完整前缀重复出现了。这种"自相似性"正是Z算法加速的核心依据。

三、Z数组的计算：线性时间算法

如果采用朴素方法计算Z数组——对每个位置 i 都从头开始逐个字符比较——那么总时间复杂度是 O(n^2)。Z算法的精妙之处在于维护一个"匹配区间" [l, r]，使得 s[l..r] 是某个前缀 s[0..r-l] 的复制，且 r 尽可能大。利用这个区间信息，可以将大量位置的Z值直接推导出来，而无需重新比较。

区间维护的核心思想

算法维护两个指针 l 和 r，表示当前已经匹配到的最右区间 [l, r]，满足 s[l..r] = s[0..r-l]（即该区间是前缀的一个副本）。初始时 l = r = 0。

对于每个 i (i > 0)，分两种情况处理：

情况A：i ≤ r（在已有区间内）

此时可以利用已知的 Z[i-l] 来初始化 Z[i]。

由于 s[l..r] = s[0..r-l]，所以 s[i..r] = s[i-l..r-l]。

令 Z[i] = min(Z[i-l], r - i + 1)，然后尝试向右扩展。

情况B：i > r（在已知区间之外）

没有任何已知信息可用，需要从 i 位置重新开始逐个字符比较。

设置 Z[i] = 0，然后暴力扩展。

无论哪种情况，在获得初步的 Z[i] 值之后，都需要尝试向右扩展：只要 s[Z[i]] == s[i + Z[i]]，就将 Z[i] 加1。扩展完成后，如果 i + Z[i] - 1 > r，就更新区间 l = i, r = i + Z[i] - 1。

Python实现

def z_function(s):
    n = len(s)
    Z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            Z[i] = min(r - i + 1, Z[i - l])
        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
    return Z

算法正确性理解：关键在于 Z[i-l] 的含义——它告诉我们从位置 i-l 开始能匹配多长的前缀。由于 s[l..r] = s[0..r-l]，位置 i 处的匹配情况应该和位置 i-l 处完全一致——至少到 r 为止。如果 Z[i-l] < r - i + 1，说明匹配在区间内就已经结束了，可以直接取用；否则需要继续向右扩展。

时间复杂度证明

Z算法的时间复杂度是 O(n)。关键在于证明每个字符最多被比较一次（严格说，每个字符最多引发一次成功比较和一次失败比较）。观察 r 指针的变化：每次成功比较都会使 r 增加至少1，而 r 最多从0增加到 n-1。因此成功比较的总次数是 O(n)。失败比较每次循环最多发生一次（即 s[Z[i]] != s[i + Z[i]] 的那一刻），而循环共有 n-1 次，所以失败比较也是 O(n)。总比较次数为 O(n)。

四、字符串匹配：Z算法的核心应用

Z算法最经典的应用是线性时间字符串匹配。给定一个模式串 P 和一个文本串 T，要找出 P 在 T 中的所有出现位置。使用Z算法解决此问题的思路非常巧妙：构建一个拼接字符串 S = P + "$" + T，其中 "$" 是一个在 P 和 T 中都不会出现的分隔符。然后计算 S 的Z数组。

为何这样做有效？对于拼接串 S 中的每个位置 i（位于 T 部分），Z[i] 表示从 i 开始的子串与 P 的最长公共前缀长度（因为是跨过分隔符与前缀进行比较）。如果 Z[i] = len(P)，就说明在文本串 T 的位置 i - len(P) - 1 处找到了一个完整的模式匹配。

def z_match(text, pattern):
    """在 text 中查找 pattern 的所有出现位置"""
    s = pattern + "$" + text
    Z = z_function(s)
    m = len(pattern)
    result = []
    for i in range(m + 1, len(s)):
        if Z[i] == m:
            result.append(i - m - 1)
    return result

# 示例
text = "abcabcabc"
pattern = "abc"
print(z_match(text, pattern))  # 输出: [0, 3, 6]

匹配过程详解（以 text="abcabcabc", pattern="abc" 为例）：

拼接串 S = "abc$abcabcabc"，长度 n = 13

计算Z数组后，在 T 部分（索引 4 到 12）检查 Z[i] == 3：

i = 5 (T[1]='b'): Z[5] = 0 ≠ 3
i = 8 (T[4]='b'): Z[8] = 0 ≠ 3
i = 11 (T[7]='b'): Z[11] = 0 ≠ 3
其他位置的 Z 值都等于 3，对应匹配位置 0, 3, 6

注意事项：分隔符的选择至关重要。分隔符必须是一个在模式串和文本串中都绝对不出现的字符。在真实场景中，如果输入可能包含任意字符（如二进制数据），可以考虑使用一个不会出现的 Unicode 码点，或改造算法使用数组下标而非字符拼接来实现同样的效果。

五、Z算法 vs KMP 对比

Z算法和KMP算法是解决字符串匹配问题的两种线性时间方案，它们在本质上是相通的，但视角不同。以下从多个维度进行系统对比：

对比维度	Z算法	KMP算法
核心数组	Z数组：后缀与前缀的LCP	π数组（前缀函数）：最长相等真前后缀
匹配策略	构造 P+$+T，在Z数组中找等于 \|P\| 的值	在T上逐字符匹配P，失配时根据π数组回退
时间复杂度	O(n + m)	O(n + m)
空间复杂度	O(n + m) 存储Z数组	O(m) 存储π数组
空间优化	可以只计算 T 部分的 Z 值，仍需 O(n)	仅需 O(m) 的额外空间
在线处理	需要完整的 T 后才能开始	可以流式处理 T
容易理解度	定义直观，容易记忆	π函数概念较抽象，但代码极简
两者关系	Z[i] 和 π[i] 可在 O(n) 内互相转换

选择建议：

需要在线（流式）匹配文本时，优先选择KMP（Z算法需要完整文本才能开始计算）
需要同时求出每个位置的最长公共前缀（LCP）信息时，Z算法可直接提供
解决字符串周期、最小覆盖子串等问题时，Z算法更直观
在只求匹配的面试场景中，两者都是满分答案，用自己最熟悉的那种即可

六、扩展应用

Z算法的应用远远不止于字符串匹配。利用Z数组携带的前缀匹配信息，可以高效解决一系列字符串处理问题。

6.1 求字符串的最小周期

如果一个字符串 s 是由某个长度为 p 的子串重复多次构成的（即 s 是周期串），那么 p 就是 s 的一个周期。利用Z数组，可以快速判断并在 O(1) 时间内求出最小周期：

def min_period(s):
    n = len(s)
    Z = z_function(s)
    for p in range(1, n):
        if n % p == 0 and Z[p] == n - p:
            return p
    return n

# 示例
print(min_period("abcabcabc"))  # 3
print(min_period("aaaaa"))       # 1
print(min_period("abcdef"))       # 6 (无周期)

原理：如果 p 是 s 的一个周期，那么 s[p..n-1] = s[0..n-p-1]，也就是说从位置 p 开始的子串与长度为 n-p 的前缀完全相同。这恰恰意味着 Z[p] >= n - p。再加上 n % p == 0（确保周期完整覆盖），即可判断。

6.2 求每个位置的最短前缀

给定一个字符串 s，对于每个位置 i，我们希望找到以 i 结尾的最短子串，使得该子串同时也是 s 的前缀。这个问题在文本压缩和模式发现中有重要应用。借助Z数组可以高效求解：

def shortest_prefix_ending_at(s):
    n = len(s)
    rev = s[::-1]
    Z_rev = z_function(rev)
    # Z_rev[i] 表示 rev[0..] 与 rev[i..] 的LCP，
    # 对应原串中 suffix 与 prefix 的关系
    result = [0] * n
    for i in range(n):
        match_len = Z_rev[n - 1 - i]
        if match_len > i + 1:
            match_len = i + 1
        result[i] = match_len
    return result

6.3 字符串压缩

给定一个字符串 s，找到它的最小压缩表示。即找到最短的字符串 t，使得 s 可以由 t 重复若干次得到（t 是 s 的最小周期子串）。这个问题其实就是求最小周期，在上面已经给出解法。

def compress(s):
    p = min_period(s)
    return s[:p]

6.4 求每个前缀的出现次数

对于字符串 s 的每个前缀 s[0..k]，计算它在 s 中作为子串出现的总次数（包括自身）。利用Z数组可以高效统计：

def prefix_occurrences(s):
    n = len(s)
    Z = z_function(s)
    cnt = [0] * (n + 1)
    for i in range(n):
        cnt[Z[i]] += 1
    for i in range(n - 1, -1, -1):
        cnt[i] += cnt[i + 1]
    result = {}
    for i in range(n):
        length = i + 1
        result[length] = cnt[length] + 1  # +1 计自身
    return result

# 示例：s = "abcabc"
# 前缀 "a": 出现2次（"a"在位置0和3）
# 前缀 "ab": 出现2次
# 前缀 "abc": 出现2次
# 前缀 "abca": 出现1次
# ...

6.5 不同子串数目

Z算法可以用于在线性时间内计算一个字符串中不同子串的数量。具体做法是：增量构建字符串，每次在末尾添加一个字符后，利用Z数组计算新增了多少个不同的子串。虽然实际中最常用后缀数组或后缀自动机解决此问题，但Z数组提供了一种简洁的替代方案。

def count_distinct_substrings(s):
    """统计字符串 s 的不同子串数量"""
    n = len(s)
    total = 0
    cur = ""
    for ch in s:
        cur += ch
        rev = cur[::-1]
        Z = z_function(rev)
        max_prefix = max(Z) if Z else 0
        # 新增的不同子串数 = 当前长度 - 最大LCP
        total += len(cur) - max_prefix
    return total

七、Z算法与KMP的转换关系

Z算法和KMP算法的核心数组（Z数组和π数组）实际上包含了等价的字符串信息，它们可以在 O(n) 时间内互相转换。理解这种转换关系，有助于从根本上把握两种算法的统一性。

7.1 从Z数组到π数组

给定Z数组，可以通过以下方式计算π数组（前缀函数）：对于每个位置 i（从1到 n-1），如果 Z[i] > 0，则对于 j = i + Z[i] - 1，有 pi[j] >= Z[i]。利用这一关系可以递推填充π数组：

def z_to_pi(Z):
    n = len(Z)
    pi = [0] * n
    for i in range(1, n):
        if Z[i] > 0:
            for j in range(i + Z[i] - 1, i - 1, -1):
                if pi[j] > 0:
                    break
                pi[j] = j - i + 1
    return pi

# 更高效的 O(n) 实现
def z_to_pi_fast(Z):
    n = len(Z)
    pi = [0] * n
    for i in range(1, n):
        pi[i] = pi[i - 1]
        while pi[i] > 0 and Z[i] <= pi[i]:
            pi[i] = pi[pi[i] - 1]
        if Z[i] > pi[i]:
            pi[i] = Z[i]
    return pi

7.2 从π数组到Z数组

反过来，从π数组也可以构造Z数组。利用 pi[i] 表示 s[0..i] 的最长相等真前后缀长度的性质，可以通过区间更新来构建Z数组：

def pi_to_z(pi):
    n = len(pi)
    Z = [0] * n
    for i in range(1, n):
        if pi[i] > 0:
            Z[i - pi[i] + 1] = max(Z[i - pi[i] + 1], pi[i])
    # 传递修正
    for i in range(1, n):
        if Z[i] > 0 and i + 1 < n:
            Z[i + 1] = max(Z[i + 1], Z[i] - 1)
    return Z

统一性理解：Z函数和π函数都是对字符串"自相似性"的量化描述。Z函数从"每个后缀与整个前缀的匹配长度"角度刻画，适合求解LCP相关问题；π函数从"每个前缀的最长相等真前后缀"角度刻画，适合递推匹配和在线处理。两者如同同一枚硬币的两面，Z数组关注"后缀"视角，π数组关注"前缀"视角，它们在O(n)时间内可以互相转化，本质上表达的是同一种字符串结构信息。

八、Z算法的Python完整实现

下面给出Z算法的完整实现，包含Z函数计算、字符串匹配和辅助工具函数：

# -*- coding: utf-8 -*-
"""Z Algorithm - 线性时间字符串匹配与模式分析工具箱"""

def z_function(s):
    """计算字符串 s 的 Z 数组（Z函数）"""
    n = len(s)
    Z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            Z[i] = min(r - i + 1, Z[i - l])
        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
    return Z


def z_match(text, pattern):
    """返回 pattern 在 text 中所有匹配的起始位置列表"""
    s = pattern + "\x00" + text
    Z = z_function(s)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(s)) if Z[i] == m]


def min_period(s):
    """返回字符串的最小周期长度"""
    n = len(s)
    Z = z_function(s)
    for p in range(1, n):
        if n % p == 0 and Z[p] == n - p:
            return p
    return n


def z_match_count(text, pattern):
    """返回 pattern 在 text 中的出现次数"""
    return len(z_match(text, pattern))


if __name__ == "__main__":
    # 测试 Z 函数
    s1 = "aaabaaab"
    print(f"s = {s1!r}")
    print(f"Z = {z_function(s1)}")

    # 测试字符串匹配
    text = "AABAACAADAABAABA"
    pattern = "AABA"
    matches = z_match(text, pattern)
    print(f"模式 '{pattern}' 在文本中的位置: {matches}")
    print(f"出现次数: {z_match_count(text, pattern)}")

    # 测试周期
    s2 = "abcabcabcabc"
    print(f"'{s2}' 的最小周期: {min_period(s2)}")

6.6 Z算法实现技巧与常见陷阱

在实际编写Z算法时，有几个细节需要特别注意：

Z[0]的处理：不同教程对Z[0]的定义存在分歧。有的定义为 n（整个串与自身的LCP），有的定义为0（约定不计）。本笔记采用 Z[0] = 0 的约定，因为这可以让代码更统一——循环从 i=1 开始，无需特殊处理 Z[0]。
区间初始化：在循环外将 l = r = 0，这样当 i=1 时满足 i > r，会进入暴力扩展分支，这是正确的——因为初始时没有任何区间信息。
边界条件：while 循环中的边界检查 i + Z[i] < n 必须在比较 s[Z[i]] == s[i+Z[i]] 之前进行，防止越界访问。
Python中的大字符串：当处理极长字符串时，Python 的 while 循环逐个比较字符可能比C/C++慢得多。对于性能敏感的场景，可以考虑使用 memoryview 或切换到C扩展。
分隔符选择：使用不可见字符如 "\x00"（空字符）比 "$" 更安全——因为在理论上模式串中也可能包含美元符号。Unicode字符 "\U00000000" 或控制字符是最佳选择。

# 处理大字符串时的优化写法
def z_function_fast(s):
    n = len(s)
    Z = [0] * n
    l = r = 0
    # 将字符串转为列表以加快索引速度（Python优化技巧）
    arr = list(s)
    for i in range(1, n):
        if i <= r:
            Z[i] = min(r - i + 1, Z[i - l])
        while i + Z[i] < n and arr[Z[i]] == arr[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] - 1 > r:
            l, r = i, i + Z[i] - 1
    return Z

九、核心要点总结

Z算法核心要点：

Z数组定义：Z[i] 表示从位置 i 开始的子串与整个字符串前缀的最长公共长度。Z[0] 通常约定为0。
线性时间计算：通过维护最右匹配区间 [l, r]，利用 Z[i-l] 的信息避免重复比较，每个字符最多被比较一次。
字符串匹配：构造 P + "$" + T，计算Z数组，Z[i] == len(P) 的位置即为匹配位置。总时间 O(n + m)。
与KMP的关系：Z函数和π函数包含等价的自我重复信息，可在 O(n) 时间内互相转换。Z函数偏向"后缀"视角，π函数偏向"前缀"视角。
最小周期：判断 Z[p] == n - p 且 n % p == 0 即可在 O(1) 时间内确定周期 p 是否成立。
扩展应用：求字符串周期、求每个前缀出现次数、不同子串计数、字符串压缩等。
空间权衡：Z算法进行字符串匹配时需要 O(n + m) 空间存放完整拼接串的Z数组，而KMP只需要 O(m) 空间存放模式串的π数组。
在线处理：Z算法不适合在线（流式）场景，因为需要完整的文本串才能开始计算；KMP可以逐字符读入文本并实时匹配。

十、进一步思考

Z算法的思想——利用已计算的信息来加速后续计算——是算法设计中"动态规划"思想的典型体现。通过维护一个"最右匹配区间"，每次计算新位置时尽可能利用已有成果，这一思路在字符串算法中反复出现（如Manacher算法计算回文半径也采用了极其相似的区间维护技巧）。

在实际工程中，Z算法和KMP算法的选择取决于具体约束。如果内存紧张且需要在线处理，KMP是更好的选择；如果代码简洁性和直观性更重要，Z算法更容易记忆和实现。值得深入思考的是：Z算法与后缀数组（Suffix Array）中的LCP数组也有深层联系，理解这种联系有助于构建完整的字符串算法知识体系。

深入研究方向：

Z算法与Manacher算法的统一框架——两者都使用区间维护技巧
Z算法在后缀自动机（SAM）构建中的应用
二维Z算法及其在图像模式匹配中的扩展
Z算法的并行化实现（GPU加速字符串匹配）
Z算法在生物信息学（基因序列匹配）中的实际应用

Z算法在面试中的常见题型

在算法面试中，Z算法通常以以下形式出现：

直接字符串匹配："实现一个函数，在字符串中查找所有匹配的模式串位置，要求 O(n+m) 时间。"
字符串周期判断："判断一个字符串是否由重复子串构成。"（LeetCode 459. Repeated Substring Pattern，可用Z数组在 O(n) 时间内解决）
最短回文串："给定一个字符串，在前面添加最少字符使其成为回文串。"（LeetCode 214. Shortest Palindrome，可以用Z算法或KMP快速求解）
前缀统计："统计字符串中每个前缀出现的次数。"利用Z数组的计数技巧可以高效完成。
基因序列匹配："在长基因序列中查找DNA片段的匹配位置，允许一定程度的变异。"

面试答题建议：

如果在面试中选择使用Z算法解决问题，建议按以下步骤展开：(1) 先用一个简单的例子（如 s="abacabac"）手动演示Z数组的计算过程，让面试官快速理解算法思路；(2) 解释区间 [l, r] 的维护逻辑，强调"利用已计算信息避免重复比较"的核心思想；(3) 用清晰的代码实现Z函数，然后在此基础上解决具体问题。重点在于展示对算法本质的理解和代码工程的规范性，语言选择上Python、Java或C++均可。

此外，建议在面试中主动提及Z算法与KMP的等价关系，这能展示你对字符串匹配算法有全局性的认识。如果面试官追问"为什么Z算法是线性时间"，可以用 r 指针单调递增的核心论点来解释——算法中每次成功比较都会让 r 增大，而 r 最多从0增加到 n-1，因此总比较次数不超过 2n 次。