KMP字符串匹配算法原理与Python实现详解

KMP算法核心原理

算法思路

Knuth-Morris-Pratt（简称KMP）算法是处理字符串匹配问题的经典方案。为了直观理解其工作机制，我们通过一个具体案例进行演示：

假设主字符串为"BBC ABCDAB ABCDABCDABDE"，我们需要判断其中是否包含子串"ABCDABD"。

匹配过程从主字符串头部开始逐个字符比对，若当前字符不匹配，则指针后移至下一个字符继续尝试。

当遇到匹配成功的字符时，算法进入内层循环，持续检查后续字符是否完全匹配。

若在匹配过程中发现最后一个字符'D'不匹配，传统暴力算法通常仅将子串向右移动一位。KMP算法的创新之处在于，它通过查询“部分匹配表”（Partial Match Table）来精确计算子串应向右移动的步数，从而跳过不必要的比对。该表的构建方法将在后文详细介绍。

以示例中的情况为例，当匹配失败时，前一个字符为'B'。查询部分匹配表可知，子串"ABCDABD"中第二个'B'对应的值为2。因此，移动步数计算公式为：已匹配字符数减去查表所得值，即 6 - 2 = 4。这意味着子串需向右移动4个位置，而非传统的1位。

随后，算法重复上述匹配与移动步骤。

这一过程持续进行，直到找到完整匹配的子串，或者主字符串剩余长度不足以容纳子串（即匹配失败）。

部分匹配表的构建逻辑

部分匹配表（Partial Match Table）

该查询表的生成逻辑如下，仍以子串"ABCDABD"为例进行推导：

对于子串"A"，其前缀和后缀均为空集，共有元素的长度为0；

对于子串"AB"，前缀为[A]，后缀为[B]，两者无交集，共有元素的长度为0；

对于子串"ABC"，前缀为[A, AB]，后缀为[BC, C]，无公共元素，长度为0；

对于子串"ABCD"，前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，无公共元素，长度为0；

对于子串"ABCDA"，前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，公共元素为"A"，长度为1；

对于子串"ABCDAB"，前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，公共元素为"AB"，长度为2；

对于子串"ABCDABD"，前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，无公共元素，长度为0。

Python代码实现

Python实现

def partial_table(p):
  '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
  prefix = set()
  res = [0]
  for i in range(1, len(p)):
    prefix.add(p[:i])
    postfix = {p[j:i + 1] for j in range(1, i + 1)}
    #print(p[:i+1],prefix,postfix,prefix & postfix or {''})
    res.append(len((prefix & postfix or {''}).pop()))
  return res

def kmp_match(s, p):
  m = len(s);
  n = len(p)
  cur = 0 # 起始指针cur
  table = partial_table(p)
  while cur <= m - n:   #只去匹配前m-n个
    for i in range(n):
      if s[i + cur] != p[i]:
        cur += max(i - table[i - 1], 1) # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
        break
    else:    
      return True # loop从 break 中退出时，else 部分不执行。
  return False

print partial_table1("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")

以上内容详细解析了KMP算法的原理及其在Python中的具体实现方式。如需获取更多关于Python实现KMP算法的参考资料，请查阅本站其他相关文章。