kmp优化模板----------------------C语言——菜鸟级

#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;
} 

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80237981