引子：BF暴力算法
KMP算法知名度相當高，燃鵝其理解難度以及代碼實現對于初學數據結構和算法的同學并不友好，經過兩天的總結，詳細總結KMP算法如下：
初學串的模式匹配時，我們都會接觸到，或者說應該能想到作為教學引子的BF暴力算法，那么先來簡單了解一哈：
我有一個大串是"abccabca",小串是"bca",現在要找到小串在大串中的位置,戰(zhàn)斗開始
①
②
③
④
⑤
⑥
⑦
⑧
這個算法理解起來肥腸簡單，我在這里假定?i?指針指向大串（主串）的首地址，j?指針指向小串（模式串）的首地址。首先大串第一位正面對比小串第一位，兩元素若相等，則兩指針分別后移，繼續(xù)比較第二位。那么這個算法被稱為暴力算法的原因就在于當兩串元素對比不相等時，j指針就會回溯到小串的首地址，這本無可厚非，而i指針卻會回溯到對比之初的后一位，比如上述第四步大小串匹配不上之后i指針馬上來到了第三位，導致了完全無用的第五和第六步比較，造成了算法時間復雜度的加大，而且主串元素數嵌套小串元素數的兩重循環(huán)，直接造成了O（m*n）的人間大慘案。雖然能實現模式匹配，但是我們的D.E.Knuth、J.H.Morris和V.R.Pratt覺得這個算法有必要改進一哈（V.R.Pratt：嚶嚶嚶），而且出于科學家的身份和*友情緣，三位同時研究出了一個船（全）新的匹配方式，KMP算法橫空出世，當然只要體驗三分鐘，你就會跟我當時一樣，放棄這個算法。
附：BF暴力算法代碼（取自《大話數據結構》? ?ps： S[0]、T[0]表示該串的長度）
第一章：kmp算法
黃歷上寫明了，這個算法不宜先學代碼，否則可能會造成理解困難。我這里還是先以一個例子來講解一下這三個外國同學的算法：
(例子取自《大話數據結構》)
不難發(fā)現，我們的模式串沒有一個字母是重復出現的，而第一步已經確診主串和模式串的前五位一模一樣，所以你如果這時候使用BF暴力算法，依次用主串的第二位到第五位跟模式串的首位正面剛，就是人傻勁大，完全莫得必要。所以我們要想個辦法避免這種重復浪費的現象，結合上面的BF例子，我們也可以明白，這種現象的出現并非是?j?指針的錯，而是?i?指針作為主串的指針瞎回溯造成的匹配浪費。
好的，理解了上面的步驟為啥子是多余的，我們再次征討一下曾被我們用了很長一段時間的暴力算法，正因為它能力有限，只能通過把?i回溯到一個很靠前的位置才能實現匹配，重點來了，這時來了一個叫做KMP的人，告訴你BF能做到的他也能做到，甚至能把時間復雜度降為O（m+n），這個時間復雜度是什么概念，意味著?i?再也不用承受眼看著無用還不得不回溯的命運。我們來看看KMP算法是怎樣干掉BF這個老黃牛的。（前方高能，佩戴腦子食用效果更佳）
要想?i?值不回溯，就一定要在?j?上面做文章，我們再次看看上面的例子，如果第一步剛發(fā)現?i=6?兩串不匹配時，摁住?i?指針，讓?i 繼續(xù)=6?，然后這時候使j指針回到初始的位置，即?i = 6 時 j = 1，讓主串中的?f?和模式串的?a?比較，就很完美遼，那這里也可能有機智的同學問，要是我的模式串中出了一個和首元素相等的元素怎么破？（/手動狗頭），不妨看看這個例子，主串是?"abcabcabx", 模式串是"abcabx"?，當然賊符合你的心意，當用BF第一輪比到第六位，發(fā)現?c?和?x?不一樣，這時你會想，把 i 回溯到第四個元素（即 a），再用?j = 1?直接就出結果。但是你想一想，可否不移動?i?,讓?j = 3?直接匹配，況且這個例子只是特殊情況，所以怎樣看來都是不必回溯?i的，下面我們看看怎樣讓?j?發(fā)揮他的作用。
既然是?j?的事，就和主串沒關系了，我們來研究一下上一段這個例子，我們剛才為什么要移動?j?讓他等于3，為了省去模式串前面存在的重復比較，這個重復比較是哪來的呢，就在于 模式串結構中的前后重復程度， "abcabx"這個例子中的串可以分為 "a"+"bcabx" 、"ab"+"cabx"、"abc"+"abx"、"abca"+"bx"、"abcab"+"x"，前綴有"a"、"ab"、"abc"、"abca"、"abcab"，定義第一個前綴重復度為0，第二個前綴重復度為1，第三個也是1，第四個我們不難發(fā)現首尾呼應，所以他的重復度較前面的加一是2，最后一個前綴ab段重復，故重復度為3。
那我們求出這個重復度有毛用呢，我們再看看那個例子，當我們在第一輪發(fā)現第六個不相等時，我們可以發(fā)現前五位重復度為3，這個3眼熟不，他可以直接在 i 不回溯的前提下把 j 帶到正確的位置，即 j = 3，那我們模式串的每一個數都需要這個值來實現KMP算法，我們用一個 next[x] 數組來儲存這些數，至于x的大小取決于你的模式串長度。
這時候我們來看看KMP算法的代碼（當然還是來自《大話數據結構》的偽碼）：
這段代碼是獲得 next數組 的
?敲了芥末多的字，希望大家可以快速理解這個KMP模式匹配算法，未完待續(xù).......
