背景
了解KMP算法的直接看證明唱矛。
字符串s,模式字符串p,想要在s中找到第一個子串等于p
窮舉解法：
p的開頭跟s的開頭比較倔幼，相等就一個個往下對比顷蟆，遇到出錯的就p往后移動一位，即p的開頭和s的第二個字符開始比钉凌。一次類推直到找到咧最。
KMP:
假設(shè)某次匹配中失敗的位置在p中是j,用S(i,j)表示S從i到j(luò)的子串，則對p有這樣的性質(zhì)：p(0,k-1) = p(j-k,j-1), 0 <= k < j御雕。語言描述為：在j的前面緊貼著一段k長度的子串矢沿，跟p開頭的長度為k子串是一樣的。
比如 abcabd, j為5時饮笛，即d的位置咨察，它前面的ab和開頭的ab相等，所以j為2福青。如果存在多種這樣的情況，k取最大的脓诡，比如aaacaaab,對最后的b而言无午，1、2祝谚、3都是成立的宪迟，取3。如果不存在這樣的交惯，則k=0次泽。而k==j的時候，等式兩邊是同一個子串席爽，沒有比較的意義了意荤。
對模式串里每一個j都有這樣的k，使用next[j]來表示只锻。
假設(shè)失敗位置在s中是i,在p中是j,KMP算法的優(yōu)化就在于玖像，失敗了之后，下一次的比較齐饮，s從i開始捐寥，p從next[j]開始。
舉例：
frabcabxabcabd 字符串s
abcabd 模式串p
在x-d位置失敗了祖驱，如果是窮舉法握恳，下一步是：
frabcabxabcabd 字符串s
abcabd 模式串p
p后移了一位，然后從頭開始比捺僻。而KMP算法是：
frabcabxabcabd 字符串s
abcabd 模式串p
失敗位置在s中是x乡洼，在p中是d,索引為5，上面分析過了d的next[5]=2。所以p從p[2]即c的位置開始比就珠，s保留上次失敗的位置寇壳，也就是x,所以就成了現(xiàn)在的樣子。
這樣一下子就跳過很多位妻怎，優(yōu)化點就在這里壳炎。
證明
看了很多網(wǎng)上的證明，它們的關(guān)注點都錯了逼侦，它們證明的是什么呢匿辩？
x a1 a2 y b
x a1 a2 x c
失敗點是最后的b-c,然后c前面的x和開頭的x是相同的，這個x就是next[j]的那一段榛丢，KMP下次比較調(diào)整后為：
x a1 a2 y b
x a1 a2 x c
KMP算法是直接從b和a1的比較開始铲球，而需要比較y和x了。這些文章的證明點就是x和y是相等的晰赞，因為失敗點是b-c,這時就說明了x和y是相等的了稼病，這一點很容易看出來。
但問題是為什么可以直接跳過這么多位置呢掖鱼？為什么移動一個位置來比較就一定會失敗呢然走？這個才是這個算法最需要證明的地方吧。就這個例子里戏挡，為什么x不用和a1比芍瑞？為什么不用和a2比呢？
示例說明：
對p有p1 p2 p3 p4 px py...,然后在px失敗了褐墅，這就意味著它之前p1-p4都是匹配到的,那假設(shè)S中對應(yīng)的字符為:p1 p2 p3 p4 s1 s2...,移動一位后：
p1 p2 p3 p4 s1 s2...
p1 p2 p3 p4 px py...
假如這個時候匹配成功拆檬，那么就有p2 p3 p4 = p1 p2 p3,根據(jù)前面對next值的定義，這時對px它的next值就是3妥凳；
再往后移一位：
p1 p2 p3 p4 s1 s2...
p1 p2 p3 p4 px py...
如果這時匹配成功竟贯，那么p3 p4=p1 p2,那px的next值就是2。而如果我們已經(jīng)知道了px的next值為1猾封，就可以判斷出這兩種情況是不可能匹配成功的澄耍。
即匹配失敗后，每往后移動一步如果成功晌缘，都有一個對應(yīng)的next值齐莲，而且這個next值是嚴格遞減的，所以知道實際的next值之后磷箕，更大的next就必定是不可能的选酗，那么之前的移動也就是不可能匹配成功的。
更小的有沒有可能岳枷？ 有芒填，因為next值是滿足條件里最大的那個呜叫，所以更小值它是可能滿足條件的。但那就是下一次匹配之后的問題了殿衰，現(xiàn)在只是剔除掉一些絕對不可能的情況朱庆。
