kmp

判断字符串a是否为字符串b的字串;

以及匹配的位置;

用next[]数组记录a的自匹配,然后用f[]数组记录a在b中的匹配;

next[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j>0&&a[i]!=a[j+1])j=next[j];
if(a[i]==a[j+1])j++;
next[i]=j;
}
for(int i=1,j=0;i<=m;i++){
while(j>0&&(j==n||b[i]!=a[j+1]))j=next[j];
if(b[i]==a[j+1])j++;
f[i]=j;
if(f[i]==n)//a在b中出现
}

原文地址:https://www.cnblogs.com/zyfltyyz/p/11719246.html