kmp优化模板


#include <stdio.h>
#include<string.h>
int next[100];
void getnext(char a[100],int n)//next值的获取 
{
  int i=0,j=-1;//初始 
  next[0]=-1;
  while(i<n)
  {
         if(j==-1||a[i]==a[j])
         { 
           j++,i++,next[i]=j;
           if(a[i]==a[j])next[i]=next[j];//优化部分 优化 优化前缀与后缀 相同 例如 abcabcabc
         }
         else j=next[j];//不匹配回溯到上一个匹配点 
  }    
}
int kmp(char a[100],char b[100],int lea,int leb)//kmp 函数 
{
    getnexth(a,lea);//next值的获取 
    int i=0,j=0,w=0;
    while(i<leb)
    {  if(j==-1||a[j]==b[i])i++,j++;
       else j=next[j];
       if(j==lea)break;
    // if(j==lea)w++,j=next[j];
    }
    if(j==lea)w=i-j+1;
    return w;

}
int main()
{  int lea,leb;    char a[100],b[100];
    while(scanf("%s%s",&b,&a)!=EOF)//b 被匹配串 a模板串 
    {
    //scanf("%s",&b);
    //scanf("%s",&a);
    lea=strlen(a);
    leb=strlen(b);
  printf("%d\n",kmp(a,b,lea,leb));
  memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
  memset(next,0,sizeof(next));
    }
return 0;
} 


  转载请注明: Five-great的博客 kmp优化模板

 上一篇
ACM省赛E题最长的递增子序列(动态规划+最长递增子序列) ACM省赛E题最长的递增子序列(动态规划+最长递增子序列)
最长的递增子序列 Bobo学会了如何计算ICPCCamp中O(nlogn)中的最长增加子序列(LIS)。 对于那些
2019-05-09
下一篇 
蓝桥杯 历届试题 对局匹配 蓝桥杯 历届试题 对局匹配
蓝桥杯 历届试题 对局匹配 问题描述   小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分,代
2019-05-07
  目录