python3 kmp 字符串匹配的方法


            先声明，本人菜鸟一个，写博客是为了记录学习的过程，以及自己的理解和心得，可能有的地方写的不好，希望大神指出。。。

抛出问题

给定一个文本串test_str（被匹配的字符串）和模式串pat_str（需要从文本串中匹配的字符串），从文本串test_str中找出模式串pat_str第一次出现的位置，没有的话返回 -1

暴力方式

在说kmp之前，我们先来讲下“暴力方式“，也就是说我们最原始的方法。　





text_str = 'asdabcdace'

pat_str = 'abcdace'



def str_match(text_str,pat_str):

  for i in range(0,len(text_str)):

    j = 1

    while j < len(pat_str):

      if text_str[i:i+j] != pat_str[0:j]: #从text_str第i个字符开始，看匹配是否成功

        break  #匹配失败，直接跳出循环，i+1，继续从第一个字符匹配

      j += 1   #匹配成功就继续匹配下一个字符，知道pat_str每个字符都匹配完

    if j == len(pat_str):

      return i

  return -1



print(str_match(text_str,pat_str))



之所以称之为暴力解法，就是因为每次匹配失败之后就将模式串，向后移动一位，从头开始匹配，一直循环下去。造成时间复杂度高，kmp也就是优化这个地方，每一次匹配失败，下次移动的距离next值



KMP

如果让我完全给你讲懂kmp算法可能不太容易，我只能大致粗略的将下它的一步步实现。我认为就一个重点，

如何求出模式串每个字符对应的next值

因为可能，每一次匹配失败的长度的字符不一样，也就对应每次移动的距离不一样，那我们如何求每个字符对应的next值，这就引出了另一个概念

最大前缀和最大后缀

　　　　

假定最大前缀=最大后缀，长度为k 那么第i位字符，对应的next值就为k+1，一次循环就能求出每个字符的next值

代码实现　　





#求字符串的next值

text_str = 'asdabcdace'

pat_str = 'abcdace'



#得到字符对应的next值

def str_next(s):

  #前两个字符默认等于1

  next = [1,1]

  for x in range(2,len(s)):

    next.append(str_max_prx(s,x,next[x-1]-1) + 1)

  return next

#参数 s字符串，匹配进行到的位置，下次开始匹配的位置

def str_max_prx(s,x,last_value):

  next = 0

  for i in range(last_value,x):

    if s[0:i] == s[x-i:x]:

      next = i

  return next

def str_match(s,m):

  next = str_next(s)

  i=0

  s_len = len(s)

  m_len = len(m)

  while i <= m_len:

    flag = True   #标志位，用来判断是否匹配成功

    index = 1

    while index <= s_len:

      if m[i:i + index] != s[0:index]:

        i = i + next[index]

        flag = False

        break

      else:

        index += 1

    if flag:

      break

  if i >= m_len:

    i = -1

  return i

res = str_match(pat_str,text_str)

print(res)



代码就是这样，很多东西可能还需要自己理解。我记个笔记，为之后方便查找，希望对你能有帮助。也希望大家多多支持中文源码网。