kmp.cpp

KMP算法的一个实例。输入目标串和模板串返回为查找成功的位置

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int *Next(string P);
	int KMP_FindPat(string S,string P,int *N);
	string S,P;
	int *N;
	cout<<"输入目标串S："<<endl;
	cin>>S;
	cout<<"输入模板串:"<<endl;
	cin>>P;
	cout<<"您输入的目标串为："<<endl;
	cout<<S;
	cout<<"您输入的目标串为:"<<endl;
	cout<<P;
	N=Next(P);
	int c=KMP_FindPat(S,P,N);
	if(c==-1) cout<<"找不到匹配的子串!"<<endl;
	else cout<<"匹配成功"<<"开始位置为："<<c<<endl;
	return 0;
}


int *Next(string P)
{
	int m=P.size();
	int *N=new int[m];
	N[0]=0;
	for(int i=1;i<m;i++)
	{
		int k=N[i-1];
		while(k>0&&P[i]!=P[k])
			k=N[k-1];
		if(P[i]==P[k])
			N[i]=k+1;
		else N[i]=0;
	}
	return N;
}

int KMP_FindPat(string S,string P,int *N)
{
	int LastIndex=S.size()-P.size();
	if(LastIndex<0)
		return (-1);
	int i;
	int j=0;
	for(i=0;i<S.size();i++)
	{
		while(P[j]!=S[i]&&j>0)
			j=N[j-1];
		if(P[j]==S[i])
			j++;
		if(j==P.size())
			return (i-j+1);
	};
	return(-1);
}