kmp_normal.cpp

实现KMP算法

#include<cstdio>
#include<cstring>
#include<time.h>
int next[512],length,comptimes;
char s[33554434];
int Normal(char*t,int pos)
{
	int i,j;
	i=pos;
	j=0;
	while(s[i]!=0&&j<length)
	{
		if(s[i]==t[j])
		{
			comptimes++;
			i++;
			j++;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j==length)
		return i-length;
	else
		return -1;
}
int KMP(char*t,int pos)
{
	int i,j;
	i=pos;
	j=0;
	
	while(s[i]!=0&&j<length)
	{
		if(j==-1||t[j]==s[i]){comptimes++;i++;j++;}
		else{j=next[j];}
	}
	if(j==length)
		return i-j;
	else
		return -1;
}
void CalcNext(char*t)
{
	int i,j;
	i=0;
	next[0]=-1;
	j=-1;
	while(i<length-1)
	{
		if(j==-1||t[i]==t[j]){i++;j++;next[i]=j;}
		else{j=next[j];}
	}
}
int main(void)
{
	char t[128];
	scanf("%s%s",t,s);

	length=strlen(t);
	CalcNext(t);

	printf("%d\n",KMP(t,0));
	printf("%d\n",Normal(t,0));
	return 0;
}