Python实现KMP字符串匹配算法详解与代码

KMP算法概述

KMP算法

KMP算法主要用于解决字符串的模式匹配问题，即在一个目标字符串中查找模式字符串首次出现的位置。

例如，

在字符串

abababc中，子串bab出现在索引1处，bc出现在索引5处。

最直观的方法是暴力匹配，即逐个字符进行比较，但其时间复杂度高达O(m*n)，效率较低。

KMP算法通过优化匹配过程，确保了整体时间复杂度为O(m+n)。

KMP算法基本原理

基本原理

举个例子：

当发现字符x与c不匹配时，进行模式串移动。

若a与x不匹配，则再次移动模式串。

此时比较到c与y， 于是下一步移动变为如下情况：

本次移动与前两次不同。前两次每次比较到长字符串的某个字符后，直接将模式串首字符与该字符对齐；而本次并未如此，原因在于y与c对齐时，y前面的ab与模式串前缀ab相同，因此无需重新比较ab，直接从第三个位置开始比较，如图：

由此可见，KMP算法针对此类情况，直接利用当前比较字符之前模式串的最长相同前后缀，将前缀与长字符串对齐，继续比较后续字符。

next数组（最长相同前后缀）计算

这里涉及KMP算法的核心：如何找到模式串中每个字符之前的最长相同前后缀？ 继续通过一个例子说明：

下方的数字记录以该字符结尾的最长相同前后缀子串的长度，初始化为0，且第一个字符对应的数字固定为0。 随后开始比较：

a与b不同，因此b对应的数字为0；同理，a与c不同，c对应的数字也为0。接下来a与a对齐，如下所示：

此时a与a相同，因此a下方的数字为1，即第二排字符串中当前比对字符索引加1。 接着b与b相同，c与a不相同，此时长字符串指针不动，模式串指针移动到当前比对位置（即c的前一位）下方数字所指的位置，如图：

移动前状态

c的前一位是b，b下方的数字是0，因此将模式串的第0位与之前的比对位置对齐，即：

当前比对位置如箭头所示，随后继续向后比较，直到遇到c与a：

此时c与a不相同，则查看模式串前一个字符下方数字所指的位置，如图：

即位置为2的地方与上方比对位置对齐：

此时c与c相同，整个字符串自比对完成：

此时可能有人疑惑，为何匹配不成功时要再比对其前一位字符下的数字位置？这是因为需要找到前一个字符位置下的最长相同前缀中的最长相同前缀。以刚才的例子：

此时a前边是abcab，所以要找到abcab的最长相同前缀，即ab，这时

然后移动到ab与ab对齐的位置继续比较即可。

时间复杂度分析

时间复杂度

简而言之，在计算模式串中每位字符之前最长相同前后缀的方法中，若模式串长度为m，则长字符串指针始终向前移动，模式串整体也始终向前移动，最终移动结果总长度不超过2m，因此比较次数最大为2m，时间复杂度为O(m)。

KMP算法运用了上述计算结果，采用类似方法进行比较和移动。若目标字符串长度为n，最长移动距离也不超过2n，因此总时间复杂度为O(m+n)。

Python代码实现

具体代码

此处未进行传入参数的验证，实际使用时需注意检查输入合法性。

def same_start_end(s):
  """最长前后缀相同的字符位数"""
  n = len(s) #整个字符串长度
  j = 0 # 前缀匹配指向
  i = 1 # 后缀匹配指向
  result_list=[0]*n
  while i < n:
    if j == 0 and s[j] != s[i]: #　比较不相等并且此时比较的已经是第一个字符了
      result_list[i] = 0  # 值为０
      i += 1 # 向后移动
    elif s[j] != s[i] and j != 0: #比较不相等,将j值设置为ｊ前一位的result_list中的值，为了在之前匹配到的子串中找到最长相同前后缀
      j = result_list[j-1]
    elif s[j] == s[i]:  #相等则继续比较
      result_list[i] = j+1
      j = j+1
      i = i+1
  return result_list
def kmp(s,p):
  """kmp算法,s是字符串，p是模式字符串，返回值为匹配到的第一个字符串的第一个字符的索引，没匹配到返回-1"""
  s_length = len(s)
  p_length = len(p)
  i = 0 # 指向s
  j = 0 # 指向p
  next = same_start_end(p)
  while i < s_length:
    if s[i] == p[j]: # 对应字符相同
      i += 1
      j += 1
      if j >= p_length: # 完全匹配
        return i-p_length
    elif s[i] != p[j]: # 不相同
      if j == 0:  # 与模式比较的是模式的第一个字符
        i += 1
      else:    # 取模式当前字符之前最长相同前后缀的前缀的后一个字符继续比较
        j = next[j]
  if i == s_length:  # 没有找到完全匹配的子串
    return -1

总结

以上所述是小编给大家介绍的python实现kmp算法的实例代码，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！