給定一個(gè)長度為n的主字符串str和一個(gè)長度為m的pattern（如str = 'qwertyuiopasdfghjkl'锐秦，pattern = 'yuiop'）崩侠，需要從str中找到被pattern命中的子串漆魔，你怎么做？
最簡單的做法：BF算法
BF是bruteforce的縮寫却音，暴力算法改抡，事實(shí)上這根本不能稱之為一個(gè)算法，基本思想就是【逐個(gè)檢查字符是否匹配系瓢，不匹配則將pattern后移一個(gè)字符位置然后繼續(xù)檢查】阿纤。每次不匹配只后移動(dòng)一個(gè)字符位置，做了很多無謂的比較夷陋，太慢了欠拾，時(shí)間復(fù)雜度O(n*m)
改進(jìn)算法：KMP算法
先說結(jié)論，KMP算法相比BF算法的改進(jìn)之處在于骗绕，每次移動(dòng)都直接移動(dòng)到下一個(gè)能夠匹配pattern的起始字符的位置藐窄，【跳步移動(dòng)】而不是一個(gè)一個(gè)字符地移動(dòng)+【不總是從首個(gè)字符開始比較，減少了無謂的比較】酬土。時(shí)間復(fù)雜度O(n+m)
1.KMP算法的基本思想——【后綴變前綴】：
以
主字符串"ababadababacambabacaddababacasdsd"（其中的斜體部分是匹配部分）
pattern串"ababaca"
為例
-
確定match_s荆忍。記主字符串str中和模式pattern已匹配的前綴串為match_s，【KMP的一切都基于這個(gè)match_s】
如撤缴，最開始時(shí)刹枉，主字符串中的已匹配的前綴串match_s為"ababa" -
尋找最長前后綴。從match_s中找出最長的相等前后綴prefix and suffix
如屈呕，match_s為"ababa"時(shí)微宝，prefix(前3個(gè)字符) = "aba" = suffix(后3個(gè)字符) - 后綴變前綴。利用prefix和suffix相等的關(guān)系虎眨，將pattern從prefix位置移動(dòng)至suffix位置蟋软，開始下一次匹配過程
完整的用例過程如下：
- 主字符串str和模式pattern首次嘗試匹配時(shí)镶摘，前5個(gè)字符匹配，得到match_s為"ababa"岳守；
- match_s為"ababa"時(shí)钉稍，prefix(前3個(gè)字符) = "aba" = suffix(后3個(gè)字符)
- 后綴變前綴。模式pattern向右移動(dòng)2個(gè)字符單位棺耍，使得pattern新的起始位置與suffix重合，開始下一次匹配過程
2.利用next數(shù)組做到后綴變前綴
通過剛才的例子种樱，pattern向右移動(dòng)2個(gè)字符單位蒙袍，可以使得pattern新的起始位置與suffix重合。那么這個(gè)2怎么得來的呢嫩挤？
很簡單
match_s = "ababa"害幅，
suffix = "aba"，len(match_s) - len(suffix) = steps => 5 - 3 = 2
因此岂昭，只需要得到match_s和最長前后綴就可以計(jì)算steps
一般地以现，使用一個(gè)長度為【m+1】的一維數(shù)組next存儲(chǔ)match_s和最長前后綴信息，next的下標(biāo)表示match_s的長度约啊，存儲(chǔ)的值表示最長(前)后綴的長度
對(duì)于pattern = "ababaca"邑遏，match_s可以是'', 'a', 'ab', 'aba', 'abab', 'ababa', 'ababac', 共7個(gè)，因此對(duì)應(yīng)next數(shù)組的長度為7
然后再把所有的match_s的最長(前)后綴的長度填入數(shù)組就大功告成
可以看到恰矩，next數(shù)組只與pattern有關(guān)记盒，而與str無關(guān)
【重點(diǎn)】next數(shù)組的填充，可以通過動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)
- 顯然外傅，next[0]和next[1]直接就是0纪吮。也就是說，next這個(gè)dp數(shù)組的初始狀態(tài)是已知的萎胰，只需要自底向上通過狀態(tài)轉(zhuǎn)移方程填滿next數(shù)組后面的空位就O了
- 對(duì)于next[i]（i >= 2）碾盟，有：next[i]對(duì)應(yīng)的match_s = next[i-1]對(duì)應(yīng)的match_s + pattern[i-1]。那么顯然也有技竟，next[i]對(duì)應(yīng)match_s的可能最長后綴suffix = next[i-1]對(duì)應(yīng)的match_s的最長后綴 + pattern[i-1]冰肴，如，'abab'的可能最長后綴 = 'aba'的最長后綴'a' + 'b' = 'ab'灵奖；那么我們要驗(yàn)證'ab'這個(gè)可能的最長后綴到底是不是真的最長后綴嚼沿。
令prefix_len = next[i-1]- 如果pattern[i-1] == pattern[prefix_len]（prefix_len的值正好標(biāo)記了對(duì)應(yīng)的match_s最長前綴的下一位置），即后綴上增加的字符 = 前綴上增加的字符瓷患，則next[i] = next[i-1] + 1
- 如果pattern[i-1] != pattern[prefix_len]骡尽，即后綴上增加的字符 != 前綴上增加的字符，那么next[i] 就不能與 next[i-1] 建立起轉(zhuǎn)移關(guān)系擅编，怎么辦攀细？事實(shí)上箫踩，next[i] 還可以嘗試與 next[i-1]之前的元素建立聯(lián)系。例如谭贪，我們可以把計(jì)算'ABCA|ABCA|B'最長前后綴的問題境钟，轉(zhuǎn)換成計(jì)算'ABCA|B'最長前后綴的問題，就是把pattern【截?cái)嘁唤亍考笫叮@樣一來next[9] = next[next[prefix_len]] + 1 = next[4] + 1 = 1 + 1 = 2慨削。如果截?cái)嘁淮稳匀徊荒芙⒙?lián)系，那就2次
計(jì)算next數(shù)組的代碼如下：
def getNextArray(pattern):
# 創(chuàng)建next數(shù)組
next_array = [0 for i in range(len(pattern))]
prefix_len = 0
# 開始填充next_array數(shù)組
for i in range(2, len(pattern)):
# 上一前綴長度
prefix_len = next[prefix_len]
# 加上prefix_len != 0是為了保證while能夠正確結(jié)束套媚，避免一直存在pattern[i] != pattern[prefix_len]產(chǎn)生死循環(huán)
while pattern[i] != pattern[prefix_len] and prefix_len != 0:
# 截?cái)鄍attern缚态，更新截?cái)嗪笊弦磺熬Y的長度
prefix_len = next[prefix_len]
if pattern[i] == pattern[prefix_len]:
prefix_len += 1
# 填充next_array[i]
next_array[i] = prefix_len
