kmp.cpp

kmp高效字符串匹配算法

#include<stdio.h>
#define MaxSize 30
struct SqString
{
	char ch[MaxSize];
	int len;
};
void GetNextval(SqString t,int nextval[]);
int  KMPIndex(SqString s,SqString t);
void main()
{
}
void GetNextval(SqString t,int nextval[])
{
	int j=0,k=-1;
	nextval[0]=-1;
	while(j<t.len)
	{
		if(k==-1||t.ch[j]==t.ch[k])
		{
			j++;k++;
			if(t.ch[j]!=t.ch[k])
				nextval[j]=k;
			else
				nextval[j]=nextval[k];
		}
		else
			k=nextval[k];
	}
}
int  KMPIndex(SqString s,SqString t)
{
	int nextval[MaxSize],i=0,j=0,v;
	GetNextval(t,nextval);
	while(i<s.len&&j<t.len)
	{
		if(j==-1||s.ch[i]==s.ch[j])
		{
			i++;j++;
		}
		else
			j=nextval[j];
	}
	if(j=t.len)
		v=i-t.len;
	else
		v=-1;
	return v;
}