学步园

其实老早就想学习KMP算法了，只不过是没机会，嘿嘿。

今天说什么也得学习学习，今天一狠劲学了，感觉，其实还是比较抽象的。。。

尤其是那个next函数。。。表示真的狠难接受，，自己捉摸了很久也弄不懂。

所以这个也就成了一个遗留问题了，还的i找别人来帮我解决，诶。。。

但是，我还是能够敲出代码。。汗。

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>


char str[1005],pat[1005];
int next[1005];
int N;
int M;
int pos;

void Next()
{
	memset(next,0,sizeof(next));
	int temp;
	for(int i=1;i<M;i++)
	{
		temp=next[i-1];
		while(temp&&pat[temp]!=pat[i])
		{
			temp=next[temp-1];
		}
		if(pat[temp]==pat[i])
			next[i]=temp+1;
		else
			next[i]=0;
	}
}

int KMP(int t)
{
	int i=t;
	int j=0;
	while(str[i]&&pat[j])
	{
		if(str[i]==pat[j])
		{
			i++;
			j++;
		}
		else if(j==0)
			i++;
		else
			j=next[j-1];
	}
	pos=i;
	if(j==M)
	{	
		return 1;
	}
	return 0;
}



int main()
{
	while(scanf("%s",str),strcmp(str,"#"))
	{
		scanf("%s",pat);
		N=strlen(str);
		M=strlen(pat);
		pos=0;
		int temp=0;
		Next();
		while(str[pos])
		{
			int ans=KMP(pos);
			temp+=ans;
		}
		printf("%d\n",temp);
	}
	return 0;
}