社区讨论

求救

P3375【模板】KMP参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo881apf
此快照首次捕获于
2023/10/27 14:17
2 年前
此快照最后确认于
2023/10/27 14:17
2 年前
查看原帖
最后一行全tle。。。 求好心人帮忙看看
CPP
#include<bits/stdc++.h>
using namespace std;
char a[100001],b[100001];
int nxt[100001];
void gn(){
	//nxt[0]=0;
	for(int i=2,j=0;i<=strlen(b+1);i++){
		while(j>0&&b[i]!=b[j+1]){
			j=nxt[j];
		}
		if(b[i]==b[j+1]){
			j++;
			nxt[i]=j;
		}
//		else{
//			nxt[i]=0;
//		}
	}
}
int main(){
	cin>>a+1;
	cin>>b+1;
	int l=strlen(b+1);
	int l2=strlen(a+1);
	//scanf("%s%s",&a+1,&b+1);
	gn();
	for(int i=1,j=0;i<=strlen(a+1);i++){
		while(j>0&&(a[i]!=b[j+1])){
			j=nxt[j];
		}
		
		if(a[i]==b[j+1]){
			j++;
		}
		//f[i]=j;
		if(j==strlen(b+1)){
			printf("%d\n",i-j+1);
			//ans.push_back();
			j=nxt[j];
		}
	}
//	for(int i=0;i<ans.size();i++){
		//printf("%d\n",ans[i]);
	//}
	for(int i=1;i<=strlen(b+1);i++){
		printf("%d ",nxt[i]);
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...