KMP算法很復(fù)雜，有很多解釋方式（DFA，前綴后綴），下面是我的一種理解。
我們在s1中匹配s2，s1、s2的長度分別為N，M
1，首先我們按順序匹配，直到匹配失敗
i表示s1的匹配起始位置，j表示s2的匹配位置
2，如果使用暴力搜索算法下一步將是這樣的：
這樣算法的復(fù)雜度是N*M
但是我們可以利用已經(jīng)匹配到的字符串（AABAA）進行優(yōu)化：
3，由于AABAA是已知的與s1無關(guān)的信息，下一步我們可以做到匹配位置（紅框）不變，i向前跳過一些字符，j變小，減少匹配長度
這種情況一共有以下幾種：
可以看出來只有C、D、E是合法的（紅框前面的部分必須匹配）
在CDE中我們只能選擇C，因為選擇D、E會跳過C這個可能的正確匹配
4，這里的C其實就是AABAA的最長前綴后綴匹配
它滿足：
1，C是一個前綴后綴匹配：AABAA的長度為n前綴和長度為n的后綴相等
2，C是n最大的前綴后綴匹配
5，在j=5的時候，最長前綴后綴匹配的長度為2
接下來要做的事情就是:
i+=(j-2)=3
j=2
而i+j=5，所以當前匹配位置維持在紅框處不變
6，所以只要我們計算出s2上面每個位置的最長前綴后綴匹配長度（前后綴匹配數(shù)組）就可以加速匹配過程了
更詳細的分析可以看出KMP算法的匹配過程時間復(fù)雜度是O(N)的
下面介紹如何計算前后綴匹配數(shù)組preSuffixArr
1,首先preSuffixArr[0]=0, 這是因為前后綴匹配不能匹配自己
2，然后preSuffixArr[n]可以按照下面的規(guī)則遞歸計算：
首先取v=preSuffixArr[n-1]，代表前n-1個字符的最長前后綴匹配：
如果s2[v+1]==s2[n], 那么可以補上這個字符，構(gòu)成一個長度為n+1的最長前后綴匹配
如果s2[v+1]!=s2[n], 繼續(xù)對v=preSuffixArr[v-1]計算這個過程
下面示例介紹如何構(gòu)造AACAABAAA的[前后綴匹配數(shù)組preSuffixArr]
k表示當前計算位置，
1，k=0,preSuffixArr[0]=0
2，k=1，然后由于s2[0]==s2[1]="A",preSuffixArr[1]=preSuffixArr[0]+1
3，k=2，v=preSuffixArr[1]=1, 由于s2[2]!=s2[1]，匹配失敗
然后v=preSuffixArr[v-1]=0, s2[2]!=s2[0], 匹配失敗preSuffixArr[2]=0
...
9，k=8，v=preSuffixArr[7]=2，s2[2]!=s2[8]，匹配失敗
v=preSuffixArr[7]=2，s2[1]!==s2[8]，匹配成功
可以證明計算前后綴匹配數(shù)組的過程時間復(fù)雜度是O(M)的，KMP算法整體時間復(fù)雜度是O(M+N)
