kmp.c

算法函数库 算法函数库

#include "stdio.h"
#include "string.h"
char s[1000000];
char p[1000000];
int next[10000000];
void next_f(char ps[])
{
	int pn=strlen(ps);
	int i=1;
	int j=0;
	next[1]=0;
	while(i<pn&&j<pn)
	{
		if(j==0||ps[i]==ps[j]){i++;j++;next[i]=j;}
		else{j=next[j];}
	}
}
int kmp(char ss[],char ps[])
{
	int sn=strlen(ss);
	int pn=strlen(ps);
	int i=0;
	int j=0;
	while(i<sn&&j<pn)
	{
		if(j==0||ss[i]==ps[j]){i++;j++;}
		else{j=next[j];}
	}
	if(j>=pn) return 1;
	else return 0;
}
int main()
{
	printf("s=");gets(s);
	printf("p=");gets(p);
	next_f(p);
	if(kmp(s,p)){printf("true\n");}
	else{printf("false\n");}
	return 0;
}