kmp算法中求next数组.txt

ACM资料大集合

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

//KMP算法中求next数组
/*
输入
ababa
cabababababac

输出
0 1 1 2 3 4 0 0 0 0 
3
*/
void getnext(char *T,int *next)
{
	next[1]=0;
	int j=1,k=0;
	while(j<=strlen(T))
	{
		if((k==0)||T[j-1]==T[k-1])
		{
			j++;
			k++;
			next[j]=k;
		}
		else
			k=next[k];
	}
}


int main()
{
	char T[10],T1[15],count=0;//T表示模版，T1表示被比较字符串
	int next[11],i,j;
	for(i=1;i<11;i++)
		next[i]=0;
	scanf("%s",T);
	scanf("%s",T1);
	getnext(T,next);
	printf("next数组为：\n");
	for(i=1;i<11;i++)
		printf("%2d",next[i]);
	printf("\n");
	for(i=0;i<strlen(T1);)
	{
		for(j=0;j<strlen(T);)
		{
			if(T1[i]!=T[j]&&j==0)
				i++;
			else if(T1[i]!=T[j])
			{
				j=next[j+1]-1;
			}
			else
			{
				i++;
				j++;
			}
		}
		if(j==strlen(T)) count++;
	}
	printf("%d\n",count);
	return 0;
}