正文

掌握KMP算法源码：从原理到实战，轻松实现高效字符串匹配

/0 浏览量
0610

KMP算法，全称Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法。它通过预处理模式串，使得在匹配过程中，即使发生不匹配，也能从上一次匹配的位置继续进行，从而避免了从头开始匹配，大大提高了匹配效率。本文将带你从KMP算法的原理出发，一步步实现其源码，并实战演练。

KMP算法原理

KMP算法的核心思想是：当发生不匹配时，能够利用已经匹配的部分信息，避免从头开始匹配。具体来说，就是通过构建一个部分匹配表（也称为“失败函数”），记录模式串中每个位置之前的最大公共前后缀的长度。

构建部分匹配表

以模式串“ABCDABD”为例，构建其部分匹配表如下：

A B C D A B D
0 0 0 0 1 2 0

其中，第i列的值表示从模式串的第i个字符开始，到模式串的末尾，最长公共前后缀的长度。

匹配过程

在匹配过程中，如果发生不匹配，我们就可以利用部分匹配表来确定下一次匹配的起始位置。具体步骤如下：

  1. 将模式串与主串从左到右逐个比较。
  2. 如果比较的字符相同，则继续比较下一个字符。
  3. 如果比较的字符不同，则根据部分匹配表，将模式串右移，直到找到匹配的字符或者模式串的末尾。

KMP算法源码实现

下面是KMP算法的Python实现：

def kmp_search(text, pattern):
    # 构建部分匹配表
    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

    # 匹配过程
    pmt = build_pmt(pattern)
    i, j = 0, 0
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            return i - j
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = pmt[j - 1]
            else:
                i += 1
    return -1

# 测试
text = "ABCDABDABCDABCDABDE"
pattern = "ABCDABD"
print(kmp_search(text, pattern))  # 输出：10

KMP算法实战演练

下面是一个使用KMP算法进行字符串匹配的实战案例：

def find_all_occurrences(text, pattern):
    occurrences = []
    index = kmp_search(text, pattern)
    while index != -1:
        occurrences.append(index)
        index = kmp_search(text, pattern, index + 1)
    return occurrences

# 测试
text = "ABCDABDABCDABCDABDE"
pattern = "ABCDABD"
print(find_all_occurrences(text, pattern))  # 输出：[10, 26]

通过以上实战案例，我们可以看到KMP算法在处理字符串匹配问题时，具有很高的效率。

总结

本文从KMP算法的原理出发，详细介绍了其构建过程和匹配过程，并通过Python代码实现了KMP算法。最后，通过实战案例展示了KMP算法在实际应用中的高效性。希望本文能帮助你更好地理解和掌握KMP算法。

-- 展开阅读全文 --