第 81 课·字符串算法进阶

KMP 字符串匹配

kmpfailure-functionpatternmatch

第81课 - KMP字符串匹配

所属模块：字符串算法 难度：intermediate 标签：kmp, failure-function, pattern, match 上一课：后缀树 下一课：Rabin-Karp 滚动哈希

学习目标

完成本课学习后，你将能够：

  1. 理解暴力字符串匹配算法（BF）的局限性，并认识到优化必要性。
  2. 解释KMP算法的核心思想：利用匹配失败时的信息，避免回溯文本指针。
  3. 掌握KMP算法中失败函数（Failure Function / Partial Match Table） 的计算原理和实现。
  4. 实现完整的KMP算法，并能分析其时间复杂度。

核心概念

1. 从暴力匹配到KMP：问题在哪？

假设我们要在文本 T 中查找模式串 P。最直观的方法是暴力匹配：用一个指针 i 遍历 T，用另一个指针 j 遍历 P。当字符匹配时，i 和 j 都递增；当不匹配时，我们将 i 回溯到本次匹配开始位置的下一个字符，并将 j 重置为0。

暴力匹配的缺陷：当 T 和 P 中有大量重复子串时，会做很多不必要的重复比较。例如，在 T = “AAAAAAB” 中查找 P = “AAAB”，每次在最后一个字符失败后，i 都要回退，导致效率低下，时间复杂度为 O(n*m)，其中 n 是文本长度，m 是模式串长度。

2. KMP的核心思想：让模式串“记住”自己

KMP算法（由Knuth, Morris, Pratt提出）的巧妙之处在于：当匹配在某个位置 P[j] 失败时，我们不回溯文本指针 i。相反，我们利用模式串 P 自身的信息，决定将模式串指针 j 移动到哪里继续匹配。

关键问题：这个“自身的信息”是什么？ 它就是最长的相等前后缀的长度。假设在 P[0…j-1] 这个子串中，最长的、既是前缀又是后缀的子串长度为 k。那么，当匹配在 j 失败时，我们可以将模式串向右滑动，使得子串 P[0…k-1] 与文本中刚刚匹配成功的部分对齐。因为 P[0…k-1] 既是前缀，又是后缀，所以它一定已经匹配过了，可以直接跳过比较。

3. 失败函数（Partial Match Table）

失败函数（通常记为 F 或 next 数组）用于存储模式串中每个位置 j 所对应的最长相等前后缀长度 k。它的定义如下：

  • F[0] = 0 （没有真前后缀）
  • 对于 j > 0，F[j] 是子串 P[0…j-1] 中最长的相等前后缀的长度。

举例说明：对于模式串 P = “ABABC”

  • j=0 (“A”): 前后缀不存在，F[0]=0
  • j=1 (“AB”): 前缀 {“A”}，后缀 {“B”}，无相等，F[1]=0
  • j=2 (“ABA”): 前缀 {“A”, “AB”}，后缀 {“BA”, “A”}，最长相等前后缀是 “A”，长度为1，F[2]=1
  • j=3 (“ABAB”): 前后缀 {“AB”} 相等，长度为2，F[3]=2
  • j=4 (“ABABC”): 前后缀无相等，F[4]=0

如何高效计算F数组？ 一个直接的想法是对每个 j，枚举所有可能的长度 k 并检查 P[0…k-1] 是否等于 P[j-k+1…j]。这效率太低。 KMP算法在计算F数组本身时也利用了递推思想，避免重复比较：

  1. 初始化 i=0, j=1, F[0]=0。
  2. 如果 P[i] == P[j]，则 F[j] = i+1，然后 i++, j++。
  3. 如果 P[i] != P[j]，且 i>0，则令 i = F[i-1] （利用已计算的信息回溯）；如果 i==0，则 F[j]=0, j++。 这个过程的时间复杂度是 O(m)。

代码示例

以下是KMP算法的完整Python实现，包含失败函数计算和字符串匹配。

def compute_failure_function(pattern):
    """
    计算模式串的失败函数（Partial Match Table）
    :param pattern: 模式串
    :return: 失败函数列表 F
    """
    m = len(pattern)
    # 初始化失败函数数组，F[0] 固定为 0
    F = [0] * m
    
    # i 指向当前最长相等前后缀的末尾（也是长度），j 指向当前正在计算的位置
    i = 0  # 相等后缀的末尾索引
    j = 1  # 从模式串的第二个字符开始计算
    
    while j < m:
        if pattern[i] == pattern[j]:
            # 匹配成功，当前位置的最长相等前后缀长度是 i+1
            F[j] = i + 1
            i += 1
            j += 1
        else:
            if i != 0:
                # 利用已经计算好的失败函数值回溯
                # 尝试寻找一个更短的、可能相等的前后缀
                i = F[i - 1]
            else:
                # i 已经为0，无法再回溯，说明没有相等前后缀
                F[j] = 0
                j += 1
    return F

def kmp_search(text, pattern):
    """
    使用KMP算法在文本中搜索模式串
    :param text: 主文本
    :param pattern: 模式串
    :return: 模式串在文本中第一次出现的起始索引，未找到返回-1
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return 0  # 空模式串总是匹配
    
    # 1. 计算失败函数
    F = compute_failure_function(pattern)
    
    # 2. 进行匹配
    i = 0  # 文本指针
    j = 0  # 模式串指针
    
    while i < n:
        if text[i] == pattern[j]:
            # 字符匹配，两个指针都前进
            i += 1
            j += 1
            if j == m:
                # 完全匹配成功，返回起始位置
                return i - j
        else:
            if j != 0:
                # 匹配失败，根据失败函数移动模式串指针
                # 不回溯文本指针 i
                j = F[j - 1]
            else:
                # 模式串指针已经在起始位置，文本指针前进
                i += 1
    return -1  # 未找到匹配

# 测试代码
if __name__ == "__main__":
    # 测试失败函数计算
    pattern1 = "ABABC"
    print(f"模式串: {pattern1}")
    print(f"失败函数 F: {compute_failure_function(pattern1)}")
    # 输出应为 [0, 0, 1, 2, 0]
    
    print("-" * 20)
    
    # 测试KMP匹配
    text = "ABABDABACDABABCABAB"
    pattern = "ABABC"
    result = kmp_search(text, pattern)
    print(f"文本: {text}")
    print(f"模式串: {pattern}")
    if result != -1:
        print(f"找到匹配，起始索引: {result}")
    else:
        print("未找到匹配")
    # 输出应为: 找到匹配，起始索引: 11

实践练习

练习 1：理解失败函数

  1. 手动计算模式串 "AABAABAAA" 的失败函数数组。
  2. 编写代码验证你的结果。
  3. 观察数组，你能发现模式串中哪些部分具有重复的模式吗？

预期输出：[0, 1, 0, 1, 2, 3, 4, 5, 2]

练习 2：查找所有匹配 修改 kmp_search 函数，创建一个新函数 kmp_find_all，返回文本中所有匹配的起始索引列表。

def kmp_find_all(text, pattern):
    # 实现这里
    pass

# 测试
text = "AAAAAA"
pattern = "AA"
print(kmp_find_all(text, pattern))  # 预期输出: [0, 1, 2, 3, 4]

练习 3：性能对比（选做） 编写一个简单的性能测试函数，比较在包含大量重复字符的文本（例如 "A" * 10000 + "B"）中查找模式串（例如 "A" * 100 + "B"）时，暴力匹配算法和KMP算法的执行时间差异。体会KMP的优势。

常见错误

  1. 失败函数计算时索引混淆：最核心的难点在于计算 F 数组时 i 和 j 的移动逻辑。初学者容易在回溯 (i = F[i-1]) 和递增 (i++, j++) 的条件上犯错。

    • 提示：i 代表的是“已匹配部分的长度”，同时也是下一个待比较字符的索引。一定要理解 F[i-1] 表示的是“上一个字符的相等前后缀长度”。

  2. 匹配时指针移动逻辑错误：在匹配阶段，当 text[i] != pattern[j] 时，应根据 j 是否为0来决定移动 j 还是移动 i。常见错误是总是移动 i，或者错误地使用 F[j] 而不是 F[j-1]。

    • 提示：当 j > 0 时，我们滑动模式串，让 P[F[j-1]] 去对齐当前的 text[i]。因为 P[0…F[j-1]-1] 这部分已经确认和文本匹配。

  3. 边界条件处理不足：没有处理模式串为空、文本为空、或模式串比文本长等情况。

    • 提示：在函数开头进行基本检查，例如 if m == 0: return 0 或 if m > n: return -1。

  4. 误用失败函数值：失败函数值 F[j] 的含义是“当在 j 处匹配失败时，应该从 P[F[j]] 重新开始比较”。在匹配代码中，失败后 j 应该更新为 F[j-1]，而不是 F[j]。

小结

本课我们学习了高效的字符串匹配算法——KMP算法。关键要点如下：

  • 问题根源：暴力匹配算法在失配时回溯文本指针，导致大量重复比较。
  • 核心思想：KMP算法通过预先计算失败函数，利用模式串自身的结构信息，使得失配时只回溯模式串指针，文本指针永不回溯。
  • 失败函数：记录了模式串每个位置的最长相等前后缀长度，是KMP算法的精髓。
  • 复杂度：预处理失败函数的时间复杂度为 O(m)，匹配阶段的时间复杂度为 O(n)，总时间复杂度为 O(m+n)，相比暴力匹配的 O(m*n) 有显著提升。
  • 应用场景：KMP适用于在较长文本中反复查找固定模式串的场景，尤其当模式串存在重复结构时优势明显。

理解KMP的关键在于理解“相等前后缀”以及如何利用这一信息避免重复劳动。虽然实现起来比暴力匹配稍复杂，但其背后的思想——利用已获得的信息指导后续搜索——是算法设计中非常重要的思想。在下一课中，我们将学习另一种基于哈希思想的字符串匹配算法：Rabin-Karp。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「Rabin-Karp 滚动哈希」 以巩固所学知识。