kmp.txt.txt

来自「在一个字符串找出是否另外一个字符串在该字符串中」· 文本 代码 · 共 57 行

#include<iostream>
#include<string>
using namespace std;
int fail(int n,string Pat)//找下一个匹配位置
{
	int lenP=Pat.length ();
	int f[10000]={0};
	f[0]=-1;
	for(int j=1;j<lenP;j++)
	{
		int i=f[j-1];
		while((Pat[j]!=Pat[i+1])&&i>=0)i=f[i];
		if(Pat[j]==Pat[i+1])f[j]=i+1;
		else
			f[j]=-1;
	};
	return f[n];
}
int KMP(string Pat,string Tar)
{
	int PosP=0;
	int PosT=0;
	int lengthP=Pat.length ();
	int lengthT=Tar.length ();
	while(PosT<lengthP&&PosT<lengthT)
	{
		if(Pat[PosP]==Tar[PosT])//逐个比较
		{
			PosT++;
			PosP++;
		}
		else if(PosP==0)
			PosT++;
		else
			PosP=fail(PosP-1,Pat)+1;
	};
		if(PosP<lengthP)return -1;
		else
			return PosT-lengthP+1;

};
int main()
{
	string pat;
	string tar;
	cout<<"Enter pat"<<endl;
	cin>>pat;
	cout<<"Enter tar"<<endl;
	cin>>tar;
	int ans=KMP(pat,tar);
	if(ans==-1)
		cout<<"匹配失败"<<endl;
	else
		cout<<"在第"<<ans<<"位匹配成功"<<endl;
	return 0;
}