1. 字符串匹配問題
假如我們有一個模式字符串ABCDABD和一個目標字符串BBC ABCDAB ABCDABCDABDE塌衰，
我們怎樣找到模式串在目標串中的匹配位置呢刨摩？
最容易想到的辦法是逐個比對：源碼
2. KMP算法背景
KMP算法是一種改進的字符串匹配算法铐望，
由D.E.Knuth扶平，J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)清女，因此人們稱它為KMP算法玩徊。
KMP算法的關鍵是利用匹配失敗后的信息的榛，
盡量減少模式串與目標串的重復匹配次數(shù)以達到快速匹配的目的琼了。
具體實現(xiàn)是利用一個事先計算好的next數(shù)組，
其中包含了模式串的前綴與后綴特征夫晌。
3. 往后跳多遠
我們觀察一下雕薪，看看逐個比對會包含哪些重復計算，然后想辦法消除它晓淀。
考慮某個中間步驟所袁，
BBC ABCDAB ABCDABCDABDE
ABCDABD
模式串ABCDABD的子串ABCDAB都比對成功了，可是凶掰，在D處失敗了燥爷。
于是下一步，我們會向后移動一個字符懦窘，繼續(xù)比對，
BBC ABCDAB ABCDABCDABDE
ABCDABD
可是畅涂，我們可以移動的更遠一些嗎港华？
能不能把目標串中的ABCDAB全都跳過？
BBC ABCDAB ABCDABCDABDE
ABCDABD
好像不行午衰，跳的太遠了立宜，我們得從這里開始冒萄，
BBC ABCDAB ABCDABCDABDE
ABCDABD
因為ABCDAB前綴和后綴包含重疊的部分。
我們稱
AB為ABCDAB的前綴和后綴的最長公共序列橙数。
跳多遠=
ABCDAB長度 - 前綴和后綴的最長公共序列長度
4. next數(shù)組
前綴和后綴的最長公共序列尊流，只和模式串有關，是模式串本身的特征灯帮。
所以奠旺，我們就可以事先算好模式串前n個字符的前綴和后綴的最長公共序列的長度，
把它們存起來施流，稱為next數(shù)組。
對于模式串agctagcagctagct來說鄙信，
它的next數(shù)組為[0,0,0,0,1,2,3,1,2,3,4,5,6,7,4]瞪醋，
即，模式串的前i+1個字符的前綴和后綴的最長公共序列的長度為next[i]装诡。
例如：agctagcagctagct的前6個字符agctag的前綴和后綴的最長公共序列的長度為next[5]=2银受。
怎樣計算這個數(shù)組呢？
我們可以利用next[0]~next[i]來計算next[i+1]鸦采。
假設pattern='agctagcagctagct'
a：next[0]=0宾巍，
ag：pattern[1]=g，pattern[0]=a渔伯，不相等顶霞，所以next[1]=0，
agc：pattern[2]=c锣吼，pattern[0]=a选浑，不相等，所以next[2]=0玄叠，
agct：pattern[3]=t古徒，pattern[0]=a，不相等读恃，所以next[3]=0隧膘，
agcta：pattern[4]=a，pattern[0]=a寺惫，相等疹吃，所以next[4]=1，
agctag：pattern[5]=g肌蜻，pattern[1]=g互墓，相等，所以next[5]=2蒋搜，
agctagc：pattern[6]=c篡撵，pattern[2]=c判莉，相等，所以next[6]=3育谬，
……
agctagcagctagc：pattern[13]=c券盅，pattern[6]=c，相等膛檀，所以next[13]=7
5. 次長公共序列
難點來了锰镀。
agctagcagctagct：pattern[14]=t，pattern[7]=a咖刃，不相等泳炉。
怎么辦？于是next[14]=0嗎嚎杨？
很顯然不行花鹅，因為agct是前綴和后綴的最長共同序列，next[14]=4枫浙。
尋找agct基于以下考慮刨肃，
如圖，橙色的A表示已經確定的最長公共序列箩帚，綠色的T將要與開頭的A后面的元素進行比較真友。
如果比對失敗，我們需要尋找次長公共序列B紧帕，然后T再與開頭的B后面元素進行比對盔然。
我們看到，三幅圖中焕参，橙色塊都是相等的轻纪，
如果存在次長公共序列，第二幅圖表明叠纷，橙色塊必然同時以B開頭且以B結尾刻帚。
即，如第三幅圖所示涩嚣，
這表明崇众，T位置的次長公共序列長度，就是橙色塊的最長公共序列長度航厚。
因此顷歌，計算agctagcagctagc的次長公共序列，就要計算B=agctagc的最長公共序列幔睬，
而這個已經計算過了眯漩，next[6]=3，得到agc。
然后與agc后面的元素t進行比對赦抖，相等舱卡，next[14]=4。
參考：
Github：kmp源碼
視頻：求kmp的next數(shù)組
從頭到尾徹底理解KMP（2014年8月22日版）
字符串匹配的KMP算法- 阮一峰的網絡日志
