KMP和扩展KMP

文章网上太多这里提一下代码细节:

KMP:

 scanf("%s\n",s);
scanf("%s\n",t);
int ls=strlen(s),lt=strlen(t);
f[]=f[]=;
for(int i=;i<lt;++i)
{
int j=f[i];
while(j&&t[j]!=t[i]) j=f[j];
if(t[j]==t[i]) f[i+]=j+;else f[i+]=;
}
int j=;
for(int i=;i<ls;++i)
{
while(j&&t[j]!=s[i]) j=f[j];
if(t[j]==s[i]) ++j;
if(j==lt) printf("%d\n",i-lt+);
}//Kmp的代码比较简单理解了就不会出错

扩展KMP:

     scanf("%s\n",s);
scanf("%s\n",t);
int ls=strlen(s),lt=strlen(t);
next[]=lt;
next[]=lt-;//第一个注意点:对自己匹配的时候是要从第1个位置开始暴力,而不是第0个
for(int i=;i<lt-;++i)
if(t[i]!=t[i+])
{
next[]=i;
break;
}
int k=;
for(int i=;i<lt;++i)
{
int p=k+next[k]-,l=next[i-k];
if(i+l<=p) next[i]=l;
else
{
int j=p-i+;
if(j<) j=;//注意这里不加会爆掉而且很难找出来
while(i+j<lt&&t[i+j]==t[j]) ++j;
next[i]=j;
k=i;
}
}
ex[]=lt;//两个串匹配则是从第0个位置开始暴力
for(int i=;i<lt;++i)
if(s[i]!=t[i])
{
ex[]=i;
break;
}
k=;
for(int i=;i<ls;++i)
{
int p=k+ex[k]-,l=next[i-k];
if(i+l<=p) ex[i]=l;
else
{
int j=p-i+;
if(j<) j=;//同上
while(i+j<ls&&j<lt&&s[i+j]==t[j]) ++j;
ex[i]=j;
k=i;
}
}

这里来手推一下扩展Kmp:

设p表示S到达的最远点,而p是由k更新到的,故p=k+ex[k]-1

故s[k..p]==t[0..p-k]

我们要求的是ex[i],所以要找出s[i]开头的一些关系,又注意到i>k,故s[i..p]==t[i-k..p-k]

而又想到应该是s[i..p]==t[0..?],因为匹配的是从0开始的,所以就涉及到了t[i-k..?]和t[0..?]的自身匹配,故引进next[i-k]表示t和t自己匹配(与ex[]一样,只不过ex[]保存的是两个字符串的匹配),设其为L,则有t[i-k..i-k+l-1]==t[0..l-1]

这里考虑:①i-k+l-1<p-k,则说明匹配到的最远的在最远点P之内,故不会涉及到我们不知道的领域,所以肯定ex[i]=l;

     ②i-k+l-1>=p-k,这就说明s[i..p]==t[0..p-i],那么接下来就从s[p+1]和t[p-i+1]开始暴力判断,并维护k和p

上一篇:Srping mvc mabatis 报错 org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):


下一篇:PCI源码学习笔记