一、原理：
KMP算法是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。朴素算法（即暴力循环）的效率太差，因为它没有好好利用比较时产生的信息，而KMP算法则运用了这一点，所以可以达到更优的复杂度。
具体的算法分析可参考：http://www.cnblogs.com/c-cloud/p/3224788.html
二、代码：
/*Sample Input:
abcegfabcd
abc Sample Output:
pos: 0
pos: 6 输入文本串T和模式串P，输出的是所有的匹配成功的位置
*/ #include<bits/stdc++.h>
using namespace std;
int next[]; void getNext(char arr[]){
int len = strlen(arr);
next[] = -;
int k = -;
int j = ; while(j < len){
if(k == - || arr[j] == arr[k]){
j++;
k++;
next[j] = k;
}
else{
k = next[k];
}
}
} void KMP(char *P, char *T){
int Plen = strlen(P);
int Tlen = strlen(T);
getNext(T);
int j = ;
for(int i = ; i < Tlen; i++){
if(T[i] == P[j]){
j++;
}
else{
j = next[j];
if(j == -) j = ;
else i--;
} if(j == Plen){
cout << "pos: " << i - Plen + << endl;
j = ;
}
}
}
int main(){
char arr1[];
char arr2[];
scanf("%s", arr1);
scanf("%s", arr2);
KMP(arr2, arr1);
}
三、分析：
1、在对模式串P[m]的处理，即求出next数组的时间花费为O（m）；
2、在进行匹配的时候，近似于对文本串T[n]从头到尾扫一遍，所以时间花费为O（n）；