字符串算法——KMP

字符串算法KMP

字符串算法

KMP算法

KMP是用来处理字符串匹配问题的

给定一个长度为 n的字符串T以及一个长度为m的字符串 P ，你需要找出 P 在 T 中出现了几次，即求出 T 的所有长度为 m 的连续子串中，和 P 相同的子串个数。

设m<=n。其中T为主串，P为模式串。

用最简易的做法处理这个问题，只需要蛮力地进行将 P 串在 T 串中进行匹配。 枚举 P 串在 T 串中的起始位置，从起始位置开始暴力地进行比对， 直到不能匹配时停止，更换下一个起始位置进行匹配。

在两个字符串都较为随机时，匹配成功部分的长度很短，这样的暴力匹配方法可以起到很好的效果。期望的时间复杂度只需要 O(n)。 但如果对两个字符串进行一些构造，上述算法的运行时间可能会很长，达到 O(nm) 级别。

模板

Luogu传送门

const int N=1000000+100;
string A,B;
int nxt[N];
inline void getnxt(string &s){
	int n=s.size(),k=0,j=-1;
	nxt[0]=-1;
	while(k<n){
		if(j<0 || s[k]==s[j]){
			k++,j++;
			nxt[k]=j;
		}
		else j=nxt[j];
	}
}
inline void KMP(string &T,string &P){
	int lt=T.size(),lp=P.size();
	int k=-1,j=-1;
	getnxt(P);
	while(k<lt){
		if((j<0 || T[k]==P[j])&& j!=lp){
			k++,j++;
			if(j==lp) cout<<k-lp+1<<endl; //*视题目情况而更改
		}
		else j=nxt[j];
	}
	for(int i=1; i<=lp; i++) cout<<nxt[i]<<" "; //*
	cout<<endl; //*
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>A>>B;
	//cout<<A.size()<<endl<<B.size()<<endl;
	KMP(A,B);
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议