kmp.cpp

kmp算法的实现

#include<iostream.h>     
#include<string>
#include<string.h>       
void get_next(char T[],int next[])
{
	//求模式串T的next函数值并存入数组next
	int i=1;
	next[1]=0;
	int j=0;
	while(i<strlen(T))
	{
		if(j==0||T[i]==T[j])
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
	for(i=1;i<=strlen(T);i++)
	cout<<next[i]<<"  ";
	cout<<endl;
}//get_next
void main()
{

	char a[100];
    int b[100];
	char flag;
	flag='y';
	while(flag=='y')
	{
	cout<<"请输入将要处理的字符串："<<endl;
	cin>>a;	
	cout<<"所得到的字符串的next函数值为："<<endl;
	get_next(a,b);
	cout<<"继续输入请按 'y',退出请按 'n' "<<endl;
	cin>>flag;
	if(flag=='n')
		break;
	}

}