在網上很容易找到分析KMP算法的部落格，但我覺得他們都沒有講到點子上去，導緻一些讀者越看越困惑，我則是看了劉汝佳的書後，自我比較通俗易懂的總結一下。
解決問題：給出字元串T和P，求P在T中第一次出現的位置，簡稱字元串比對。
算法準備：最單純的模拟算法就是每次枚舉起始點，再判斷是否比對，效率O(nm),極低。
但根據經驗，任何一個高效算法的提出就是減少的備援狀态，在模拟過程中，很明顯做了一次又一次重複的事情，我們應該想辦法避免重複。
分析：
T=‘ABRACADABRACABRACABRAE’
P=‘ABRAE’
首次比對，發現T[4]='C',P[4]='E',導緻比對失敗，簡稱失配，
然後根據模拟算法，接着我們又從T[1],P[0]開始重新比對，但是明顯我們沒有用到第一次比對時得到的資訊，其實第一次比對時，我們就知道T[1]和P[1]相等，T[0]和P[0]相等，如果我們能提前處理出P[1]與P[0]是否相等，我們就可以判斷是接着比對T[2]和P[1]，還是重新開始下一個輪T[2]與P[0]的比對。
是以，我們有了一個思路：
對于字元串P，提前預處理出f[i]表示目前P[i]與前面哪個j對應的P[j]相等。
但很快我們發現，這在最壞情況下這并不能使效率提升多少。
再次深度分析：
當我們一次比對進行到P[j],T[i]，而P[j]不等于T[i],導緻失配，但我們已經已經知道P[j-1]等于T[i-1]，我們可以在P中直接找與P[j-1]等效的地方P[k]重新開始比對T[i-1]，顯然k<j,
若k>j,P[j]與T[i]并不相等，是以一定失配。
顯然f數組中仍儲存了大量的備援資訊
那麼什麼是等效？ 等效的P[j]和P[k]即指P(1...k)=P(j-k+1....j)
是以我們可以預處理出f[j]表示與P[j]等效的P[k]的位置，那麼失配後，
我們在j前面找到與P[j-1]等效的地方P[k],同時P[k+1]=T[i]。然後接着比對P[k+2]與T[i+1],如果找不到對應的k，顯然此次比對是失敗的，需要從頭開始。
這就是KMP算法，很簡單吧？但同時似乎效率并不高，因為有兩層循環，且第二層在極端情況下好像是會退化的，真的是這樣麼？
可以這樣計算時間複雜度：每一次比對成功都會有j++,i++，而每一次j=f[j](即找到前一個與P[j-1]相等的地方)都會使j最少-1，但由于j最多隻會增加n次，是以j=f[j]的次數最多也隻有n次。是以效率為O(n)。
參考程式：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=11000;
int f[maxn];
char P[maxn],T[maxn];
int n,m;
void getfail(char* P,int* f){
f[0]=0;f[1]=0;
for (int i=1;i<m;i++){
int j=f[i];
while (j && P[i]!=P[j])j=f[j];
f[i+1]=P[i]==P[j]?j+1:0;
}
}
int find(char* P,char* T,int* f){
int j=0;
for (int i=0;i<n;i++){
while (j && T[i]!=P[j])j=f[j];
if (P[j]==T[i])j++;
if (j==m)return i-m+1;
}
return -1;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s%s",T,P);
getfail(P,f);
printf("%d\n",find(P,T,f));
return 0;
}