hdoj2087——KMP的应用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void get_next(char b[], int *next)
{
     int i = 0;
     int j = -1;
     next[0] = -1;
     int len_b = strlen(b);
     while(i < len_b - 1)
     {
         if(j == -1 || b[i] == b[j])
         {
             ++i;
             ++j;
             next[i] = j;
         }
         else
         {
             j = next[j];
         }
     }
	 return;
}
int kmp(char a[], char b[], int next[])
{
     int i = 0;
     int j = 0;
     int len_a = strlen(a);
     int len_b = strlen(b);
     while(i < len_a && j < len_b)
     {
         if(j == -1 || a[i] == b[j])
         {
             ++i;
             ++j;
         }
         else
         {
             j = next[j];
         }
     }
     if(j >= len_b)
     {
         return i - len_b;
     }
     else
     {
         return -1;
     }
 }
int solve(char s[],char t[],int len,int next[])
{
	int ans=kmp(s,t,next);
	if(ans==-1)
		return 0;
	return 1+solve(s+ans+len,t,len,next);
}
int main()
{
	char s[1010],t[1010];
	scanf("%s",s);
	getchar();
	while(strcmp("#",s)!=0)
	{
		gets(t);
		int next[1010];
		get_next(t,next);
		int len=strlen(t);
		int ans=solve(s,t,len,next);
		printf("%d\n",ans);
	
		scanf("%s",s);
		getchar();
	}


//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>