一、原理：

　　KMP算法是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。朴素算法（即暴力循环）的效率太差，因为它没有好好利用比较时产生的信息，而KMP算法则运用了这一点，所以可以达到更优的复杂度。

　　具体的算法分析可参考：http://www.cnblogs.com/c-cloud/p/3224788.html

二、代码：

1 /*Sample Input: 2   abcegfabcd 3   abc 4    5   Sample Output: 6   pos: 0 7   pos: 6 8  9   输入文本串T和模式串P，输出的是所有的匹配成功的位置 10 */11 12 #include
      
       13 using namespace std;14 int next[10010];15 16 void getNext(char arr[]){17     int len = strlen(arr);18     next[0] = -1;19     int k = -1;20     int j = 0;21     22     while(j < len){23         if(k == -1 || arr[j] == arr[k]){24             j++;25             k++;26             next[j] = k;27         }28         else{29             k = next[k];30         }31     }32 }33 34 void KMP(char *P, char *T){35     int Plen = strlen(P);36     int Tlen = strlen(T);37     getNext(T);38     int j = 0;39     for(int i = 0; i < Tlen; i++){40         if(T[i] == P[j]){41             j++;42         }43         else{44             j = next[j];45             if(j == -1) j = 0;46             else i--;47         }48         49         if(j == Plen){50             cout << "pos: " << i - Plen + 1 << endl;51             j = 0;52         }53     }54 }55 int main(){56     char arr1[20];57     char arr2[5];58     scanf("%s", arr1);59     scanf("%s", arr2);60     KMP(arr2, arr1);61 }
      

 

三、分析：

    1、在对模式串P[m]的处理，即求出next数组的时间花费为O（m）；

    2、在进行匹配的时候，近似于对文本串T[n]从头到尾扫一遍，所以时间花费为O（n）；