python3 kmp 字符串匹配的方法

更新時(shí)間：2018年07月07日 15:25:22 作者：7749ha

這篇文章主要介紹了python3 kmp 字符串匹配的方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

先聲明，本人菜鳥(niǎo)一個(gè)，寫博客是為了記錄學(xué)習(xí)的過(guò)程，以及自己的理解和心得，可能有的地方寫的不好，希望大神指出。。。

拋出問(wèn)題

給定一個(gè)文本串test_str（被匹配的字符串）和模式串pat_str（需要從文本串中匹配的字符串），從文本串test_str中找出模式串pat_str第一次出現(xiàn)的位置，沒(méi)有的話返回 -1

暴力方式

在說(shuō)kmp之前，我們先來(lái)講下“暴力方式“，也就是說(shuō)我們最原始的方法?！?/p>

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個(gè)字符開(kāi)始，看匹配是否成功
        break  #匹配失敗，直接跳出循環(huán)，i+1，繼續(xù)從第一個(gè)字符匹配
      j += 1   #匹配成功就繼續(xù)匹配下一個(gè)字符，知道pat_str每個(gè)字符都匹配完
    if j == len(pat_str):
      return i
  return -1

print(str_match(text_str,pat_str))

之所以稱之為暴力解法，就是因?yàn)槊看纹ヅ涫≈缶蛯⒛Ｊ酱?，向后移?dòng)一位，從頭開(kāi)始匹配，一直循環(huán)下去。造成時(shí)間復(fù)雜度高，kmp也就是優(yōu)化這個(gè)地方，每一次匹配失敗，下次移動(dòng)的距離next值

KMP

如果讓我完全給你講懂kmp算法可能不太容易，我只能大致粗略的將下它的一步步實(shí)現(xiàn)。我認(rèn)為就一個(gè)重點(diǎn)，

如何求出模式串每個(gè)字符對(duì)應(yīng)的next值

因?yàn)榭赡?，每一次匹配失敗的長(zhǎng)度的字符不一樣，也就對(duì)應(yīng)每次移動(dòng)的距離不一樣，那我們?nèi)绾吻竺總€(gè)字符對(duì)應(yīng)的next值，這就引出了另一個(gè)概念

最大前綴和最大后綴

假定最大前綴=最大后綴，長(zhǎng)度為k 那么第i位字符，對(duì)應(yīng)的next值就為k+1，一次循環(huán)就能求出每個(gè)字符的next值

代碼實(shí)現(xiàn)　　

#求字符串的next值
text_str = 'asdabcdace'
pat_str = 'abcdace'

#得到字符對(duì)應(yīng)的next值
def str_next(s):
  #前兩個(gè)字符默認(rèn)等于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
#參數(shù) s字符串，匹配進(jìn)行到的位置，下次開(kāi)始匹配的位置
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   #標(biāo)志位，用來(lái)判斷是否匹配成功
    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)

代碼就是這樣，很多東西可能還需要自己理解。我記個(gè)筆記，為之后方便查找，希望對(duì)你能有幫助。也希望大家多多支持腳本之家。

您可能感興趣的文章: