KMP算法模板+next数组性质扩展KMP模板

KMP算法模板

#include<bits/stdc++.h>
using namespace std;
char s[10010],k[10010];
int nex[10010],f[10010];
int n,m;
void getnext(){
 nex[1]=0;
 for(int i=2,j=0;i<=n;++i){
  while(j>0&&s[i]!=s[j+1])j=nex[j];
  if(s[i]==s[j+1])j++;
  nex[i]=j;
 }
}

void KMP(){
 for(int i=1,j=0;i<=m;++i){
  while(j>0&&(j==n||k[i]!=s[j+1]))j=nex[j];
  if(k[i]==s[j+1])j++;
  f[i]=j;
 }
}

int main(){
 cin>>n;
 srand(time(NULL));
 for(int i=1;i<=n;++i){
  s[i]=rand()%3+'a';
 }
 printf("%s\n",s+1);
 getnext();
 for(int i=1;i<=n;++i)
 printf("%d ",nex[i]);
 printf("\n");
 scanf("%d",&m);
 for(int i=1;i<=m;++i){
  k[i]=rand()%3+'a';
 }
 printf("%s\n",k+1);
 KMP();
 for(int i=1;i<=m;++i)
 printf("%d ",f[i]);
 printf("\n");
}

KMP算法中next数组的性质->求循环节

就算法本身的匹配其实应用比较简单，对于KMP算法，其实重点是它的next数组。next数组的一个重要应用就是求循环节，注意，这里的循环节有很多。一般能够分为最小循环节和一般循环节。

1.最小循环节：根据next数组的定义，它是表示字符串去掉第一个字符的到达i点的后缀与整个字符串的最大匹配。举个例子：

abababa 他的next数组就是0 0 1 2 3 4 5。当然也就表示与其匹配的位置。例如next数组的第三个数字为1，表示它和1号位的字符匹配。综上，根据定义，一个由循环的字符串，他的len（字符串长度或者说最后一个字符的位置）-nex[len]就是最小循环节的长度。读者可以试着证明一下，过程很好理解。最小循环节是最基本的，也是最简单的。当字符串不循环的时候，它的最小循环节就是它自己。

2.所有循环节：再用上述的例子，我们根据len-nex[len]求出了最小循环节，但是很显然，这个字符串本身就可以视为一个循环节，还有，还有abab,ababab,也是它的循环节。放一起，它的循环节分别为ab,abab,ababab,abababa ，一共有4个，那么怎么来求一个字符串的所有循环节呢？

先贴一个代码：

int i=len;
while(i){
    printf("%d ",len-nex[i]);
    i=nex[i];
}

通过迭代i=nex[i]可以使i依次减少一个循环节：例如上面，nex[7]=5,nex[5]=3,nex[3]=1,nex[1]=0; 从而用len-nex[i]得到循环节长度分别为7-nex[7]=2, 7-nex[5]=4,7-nex[3]=6,7-nex[1]=7; 循环结束。

扩展kMP模板

关于扩展KMP算法，这里附一个刘雅琼的PPT，提取码：w1f3

#include<bits/stdc++.h>
using namespace std;
char s[10010],s1[10010];
int nex[10010],ext[10010];
int n,m;

void getnext(){
 int a,p,i,j(-1);//j(-1)等于j=-1， 赋值的意思 
 nex[0]=n;
 for(i=1;i<n;++i,--j){
  if(j<0||i+nex[i-a]>=p){
   if(j<0)j=0,p=i;
   while(p<n&&j<n&&s[p]==s[j])p++,j++;
   nex[i]=j,a=i;
  }
  else nex[i]=nex[i-a];
 }
}

void exKMP(){
 int a,p,i,j(-1);
 for(int i=0;i<m;++i,--j){
  if(j<0||i+nex[i-a]>=p){
   if(j<0)j=0,p=i;
   while(p<m&&j<n&&s1[p]==s[j])p++,j++;
   ext[i]=j,a=i;
  }
  else ext[i]=nex[i-a];
 }
}

int main(){
 srand(time(NULL));
 cin>>n>>m;
 for(int i=0;i<n;++i)s[i]=rand()%3+'a',printf("%c",s[i]);
 puts("");
 for(int i=0;i<m;++i)s1[i]=rand()%3+'a',printf("%c",s1[i]);
 puts("");
 getnext();
 exKMP();
 for(int i=0;i<n;++i)
 printf("%d ",nex[i]);
 puts("");
 for(int i=0;i<m;++i)
 printf("%d ",ext[i]);
 puts("");
}

KMP算法模板+next数组性质 扩展KMP模板

KMP算法模板+next数组性质扩展KMP模板