kmp字符串匹配.txt

KMP字符串匹配的c实现

#include<iostream.h>
#include<string.h>

int next[20];


int main(){
	char a[20]="abcdefghijk";
	char b[20]="abcdefgg";
	int i,j;
	i=0;next[0]=0;j=0;
	while(i<strlen(b))
	{
		if(j==0||b[i]==b[j])
		{
			++i;++j;
			if(b[i]!=b[j])
				next[i]=j;
			else
				next[i]=next[j];
		}
		else
			j=next[i];
	}
	i=0;j=0;
	while(i<strlen(a)&&j<strlen(b))
	{
		if(j==0||a[i]==b[j])
		{
			++i;++j;
		}
		else
			j=next[j];
	}
	if(j>=strlen(b))
		cout<<i-strlen(b);
	else
		cout<<"-1";
	return 0;
}