kmp_match.cpp

常用算法与数据结构原代码

#include <iostream.h>

void faillink(char *p,int next[])
{
	int j,k;
	next[0]=-1;
	j=1;
	do{
		k=next[j-1];
		while (k!=-1 && p[k]!=p[j-1])
			k=next[k];
		next[j++]=k+1;
	}
	while (p[j]!='\0');
}

int kmp_match(char *t,char *p,int next[])
{
	int k,j;
	if (*t=='\0')
		return 0;
	for (k=j=0;t[k]!='\0';)
	{
		while (j!=-1 && p[j]!=t[k])
			j=next[j];
		k++;
		j++;
		if (p[j]=='\0')
			return k-j;
	}
	return -1;
}

void main()
{
	char t[]="abccbcbacb";
	char p[]="ccbcb";
	int next[20];
	faillink(p,next);
	cout<<kmp_match(t,p,next)+1<<endl;
}