1，什么是kmp算法
kmp算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱(chēng)它為克努特——莫里斯——普拉特操作（簡(jiǎn)稱(chēng)KMP算法）。簡(jiǎn)而言之就是在一串字符串中找尋一串子串。
基本思想：
設(shè)主串后面用m表示(長(zhǎng)度為m)：a b a c a a b a c a b a c a b a a b b
模式串后面用n表示(長(zhǎng)度為n)：? a b a c a b
如過(guò)使用暴力算法匹配模式串在主串的位置，則先是是m[0]，n[0]對(duì)比，一樣下表就同時(shí)往后移一位，繼續(xù)對(duì)比，如果不一樣，此時(shí)m從第二位開(kāi)始和n進(jìn)行匹配，繼續(xù)剛才的操作，直到找到為止，這種方式極大的降低匹配效率，時(shí)間復(fù)雜度為O(mn)。
kmp算法就是為了在比較中讓模式串盡量右移，從而達(dá)到提高效率效果。假設(shè)m是個(gè)char[],n也是，m[i]和n[j]進(jìn)行比較,如上圖，前面五位都相同,第6位開(kāi)始出現(xiàn)差異。此時(shí)我們就要向右移動(dòng)n，那么要向右移動(dòng)幾位呢。我們看mn前面5位都是相同的,a b a c a 的前綴和后綴只有一個(gè)a是相同的。對(duì)應(yīng)的m中前面五位也只有一個(gè)長(zhǎng)度為一的前綴和后綴a,
所以我們將n整體右移到m[4]的位置，變成
a b a c a a b a c a b a c a b a a b b
? ? ? ? ? ? a b a c a b
當(dāng)比較到第二位又出現(xiàn)不等的情況，此時(shí)的n右移一位就行比較，此時(shí)已經(jīng)在m中找到了n所在的位置，然后將a的下表返回。這就是大概思路，這樣比較我們只進(jìn)行3次比對(duì)，就出了結(jié)果。時(shí)間復(fù)雜度為O(m+n)。
a b a c a a b a c a b a c a b a a b b
? ? ? ? ? ? ? ?a b a c a b
現(xiàn)在我們來(lái)看看n的移動(dòng)規(guī)則怎么來(lái)的，其實(shí)就找abacab中每一位到前綴中存在的最大長(zhǎng)度的相等的前后綴，分析一下
a b a c a b
用一個(gè)next[]來(lái)保存計(jì)算出的值，n[0]本來(lái)就是前綴，所以為next[0]=0，n[0],n[1]對(duì)比不相等,所以n[1]b的相同的前綴也為0,next[1]=0，然后n[0]和n[2]對(duì)比相同，所以next[2]就是n[0]在next[]中對(duì)應(yīng)的下標(biāo)next[0]+1，所以next[2]=1;此時(shí)n[0]就不需要在和后面對(duì)比，從第二位n[1]=b開(kāi)始接著對(duì)比，n[1]和n[3]進(jìn)行對(duì)比，不相等，此時(shí)代表ab和ac不相等了，所以我們的下標(biāo)又要回退到n[1]的前一位也就是n[0]在next[]數(shù)組中所對(duì)應(yīng)的值，所以現(xiàn)在是n[0]和n[3]進(jìn)行對(duì)比ac不等，此時(shí)n[0]已經(jīng)不能往前移動(dòng)，所以n[3]對(duì)應(yīng)的next[3]值為0，然后n[0]繼續(xù)對(duì)比n[4]，aa相等，根據(jù)上面的分析得出next[4]=0+1(前綴a的下標(biāo)加一)，前后a相等已經(jīng)找到所以開(kāi)始對(duì)比n[1]和n[5]為bb相等，所以next[5]=1+1(前綴b的下標(biāo)加一)，最后得到next={0,0,1,0,1,2},在一次說(shuō)明2的含義，就是存在一個(gè)長(zhǎng)度為2相等的前后綴，這里就是ab;
代碼如圖
目標(biāo)串 a b a c a a b a c a b a c a b a a b b
模式串 a b a c a b
next值 0 0 1 0 1 2?
第六位ab不等，b的前一位a的next值為1
目標(biāo)串 a b a c a?a?b a c a b a c a b a a b b
模式串? ? ? ? ? ? ?a b?a c a b
此時(shí)m[5]!=n[1],重復(fù)
以上步驟，b的前一位a的next值為0，繼續(xù)右移，最后相等，返回a的坐標(biāo)，這就是kmp算法了
目標(biāo)串 a b a c a?a?b a c a b a c a b a a b b
模式串? ? ? ? ? ? ? ? a?b?a c a b
