先聲明，本人菜鳥一個，寫博客是為了記錄學習的過程，以及自己的理解和心得，可能有的地方寫的不好，希望大神指出。。。
拋出問題
給定一個文本串test_str（被匹配的字符串）和模式串pat_str（需要從文本串中匹配的字符串），從文本串test_str中找出模式串pat_str第一次出現的位置，沒有的話返回 -1
暴力方式
在說kmp之前，我們先來講下“暴力方式“，也就是說我們最原始的方法?！?/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個字符開始，看匹配是否成功
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)
代碼就是這樣，很多東西可能還需要自己理解。我記個筆記，為之后方便查找，希望對你能有幫助。也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
