1 #include <cstring> 2 #include <iostream> 3 using namespace std; 4  5 void get_next(const char *ptrn,int plen,int *next) 6 { 7     int i=0; 8     next[i]=-1; 9     int j=-1;10     while(i<plen-1)11     {12         if(j==-1||ptrn[i]==ptrn[j])13         {14             ++i;15             ++j;16             if(ptrn[i]!=ptrn[j])17                 next[i]=j;18             else19                 next[i]=next[j];20         }21         else22             j=next[j];23     }24 }25 26 int kmp_search(const char *src,int slen,const char *patn,int plen,const int *next,int pos)27 {28     int i=pos;29     int j=0;30     while(i<slen&&j<plen)31     {32         if(j==-1||src[i]==patn[j])33         {34             ++i;35             ++j;36         }37         else38         {39             j=next[j];40         }41     }42     if(j>=plen)43         return i-plen;44     else45         return -1;46 }47 48 int main()49 {50     char src[]="aabcabcebafabacabceabcaefabcacdabcab";51     char prn[]="abac";52     int slen=strlen(src);53     int plen=strlen(prn);54     int* next=new int[plen];55     get_next(prn,plen,next);56     for(int i=0;i<plen;++i)57         cout<<next[i]<<" ";58     cout<<endl;59     cout<<"result sub str: "<<kmp_search(src,slen,prn,plen,next,0)+1<<endl;60     delete []next;61     return 0;62 }