站外题kmp模板求助
  • 板块学术版
  • 楼主yx20240301
  • 当前回复15
  • 已保存回复15
  • 发布时间2022/7/21 10:31
  • 上次更新2023/10/27 19:09:29
查看原帖
站外题kmp模板求助
631104
yx20240301楼主2022/7/21 10:31

蒟蒻爆了很久的零了,求大佬帮调。

题目:there

代码:

#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int nex[maxn];
int Getnext(string t) {
	int j=0,k=-1,num=0;
	nex[j] = k;
	while(j<(t.length()-1)) {
		if(k==-1||t[j]==t[k]){
			j++;
			k++;
			nex[j]=k;
			num++;
		} else k=nex[k];
	}
	return nex[num];
}
void kmp(string text,string key) {
	int num=0,cnt=0;
	int nextt=Getnext(key);
	int i=0,j=0,thenext=text.length(),keylen=key.length();
	while (i<=thenext-keylen){
		if (j==-1||text[i+j]==key[j]) ++j;
		else{
			i+=j-nex[j];
			j=nex[j];
			num++;
		}
		if (j==keylen){
			cout<<num+j<<" ";
			cnt++;
		} 
	}
	if(cnt==0)	cout<<0;
}
int main(){
	int n;
	string b;
	scanf("%d",&n);
	cin>>b;
	for(int i=1;i<=n;i++){
		string a;
		cin>>a;
		kmp(a,b);
		cout<<'\n';
	}
	return 0;
}

提交记录

直接套的模板,但是错了,我太弱了

2022/7/21 10:31
加载中...