KMP算法

KMP算法用于解决字符串匹配问题, str1 某个字符串是否与 str2 一样, 如果一样, 返回 str2 开始的位置

//KMP算法模板

int n,m;
char s[N],p[M];
int ne[M];
//s[]是长文本,p[]是模式串(短串),n是s的长度,m是p的长度

//读入字符串
cin>>n>>s+1>>m>>p+1;  //KMP算法习惯下标从1开始

//求模式串的next数组
for(int i=2,j=0;i<=m;i++)
{
    while(j&&p[i]!=p[j+1])j=ne[j];
    if(p[i]==p[j+1])j++;
    ne[i]=j;
}

//KMP匹配过程
for(int i=1,j=0;i<=n;i++)
{
    while(j&&s[i]!=p[j+1])j=ne[j];
    if(s[i]==p[j+1])j++;
    
    if(j==m) //匹配成功
    {
        j=ne[j];
    }
}