1 /*                 核心代码      */ 2  3  4  5 #include<iostream> 6 #include<string> 7  8 using namespace std; 9 const int N=100005;10 11 void getNext(string p,int *next)12 {13     int j,k;14     next[0]=-1;15     j=0;16     k=-1;17     while(j<p.length()-1)18     {19         if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]20         {21             j++;22             k++;23             next[j]=k;24         }25         else                   //p[j]!=p[k]26             k=next[k];27     }28 }29 30 31 int KMPMatch(string s,string p)32 33 34 {35     int next[100];36     int i,j;37     i=0;38     j=0;39     getNext(p,next);40     while(i<s.length())41     {42         if(j==-1||s[i]==p[j])43         {44             i++;45             j++;46         }47         else48         {49             j=next[j];       //消除了指针i的回溯50         }51         if(j==p.length())52             return i-p.length();53     }54     return -1;55 }