跳到主要内容

KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在主字符串中查找子字符串的位置。它的核心思想是通过预处理子字符串，避免在匹配失败时进行不必要的回溯，从而提高搜索效率。

为什么需要KMP算法？​

在传统的字符串匹配算法中，当匹配失败时，主字符串的指针会回退到起始位置的下一个字符，重新开始匹配。这种方法的时间复杂度为O(m*n)，其中m是主字符串的长度，n是子字符串的长度。对于较长的字符串，这种算法的效率较低。

KMP算法通过预处理子字符串，构建一个部分匹配表（Partial Match Table，简称PMT），在匹配失败时利用该表跳过不必要的比较，从而将时间复杂度降低到O(m+n)。

KMP算法的核心思想​

KMP算法的核心在于部分匹配表（PMT）。PMT记录了子字符串中每个位置的最长公共前后缀的长度。通过这个表，算法可以在匹配失败时快速确定子字符串的移动距离，避免主字符串指针的回退。

什么是前后缀？​

  • 前缀：从字符串开头到某个位置的子字符串（不包括最后一个字符）。
  • 后缀：从某个位置到字符串末尾的子字符串（不包括第一个字符）。

例如，对于字符串 "ABCDABD"：

  • 前缀包括："A", "AB", "ABC", "ABCD", "ABCDA", "ABCDAB"
  • 后缀包括："BCDABD", "CDABD", "DABD", "ABD", "BD", "D"

部分匹配表（PMT）的构建​

以子字符串 "ABCDABD" 为例，其PMT如下：

字符位置字符最长公共前后缀长度
0A0
1B0
2C0
3D0
4A1
5B2
6D0
备注

注意：PMT的长度比子字符串的长度少1，因为第一个字符没有前缀。

KMP算法的实现​

步骤1：构建部分匹配表​

python
def build_pmt(pattern):
    pmt = [0] * len(pattern)
    j = 0  # 前缀指针
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pmt[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pmt[i] = j
    return pmt

步骤2：利用PMT进行匹配​

python
def kmp_search(text, pattern):
    pmt = build_pmt(pattern)
    j = 0  # 子字符串指针
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = pmt[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1  # 返回匹配的起始位置
    return -1  # 未找到匹配

示例​

python
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = kmp_search(text, pattern)
print("匹配位置：", result)

输出：

匹配位置： 10

实际应用场景​

KMP算法广泛应用于以下场景：

  1. 文本编辑器：在文档中查找特定单词或短语。
  2. 生物信息学：在DNA序列中查找特定的基因片段。
  3. 搜索引擎：在网页内容中快速定位关键词。

总结​

KMP算法通过预处理子字符串，构建部分匹配表，避免了不必要的回溯，从而显著提高了字符串匹配的效率。它的时间复杂度为O(m+n)，适用于处理较长的字符串。

提示

练习：

  1. 尝试手动构建字符串 "AABAACAABAA" 的部分匹配表。
  2. 修改KMP算法，使其返回所有匹配的位置，而不仅仅是第一个匹配的位置。

附加资源​