KMP

　KMP const int maxn=1000000+5; int nxt[maxn]; void get_next(string s) {

　 nxt[0]=-1;

　 int k=-1,q=1,len=s.length();

　 while(q<len)

　 {

　 while(k>-1&&s[k+1]!=s[q])k=nxt[k];

　 if(s[k+1]==s[q])k++;

　 nxt[q++]=k;

　 } } int kmp(string s1,string s2) {

　 get_next(s2);

　 int q=0,k=-1;

　 int len1=s1.length(),len2=s2.length();

　 while(q<len1)

　 {

　 while(k>-1&&s1[q]!=s2[k+1])k=nxt[k];

　 if(s1[q]==s2[k+1])k++;

　 q++;

　 if(k==len2-1)return q-k;

　 }

　 return -1; }

推荐访问:KMP