KMP
来源：托福 发布时间：2021-03-05 点击：
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