社区讨论

赋值问题

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

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lye125md
此快照首次捕获于
2024/07/09 14:25
2 年前
此快照最后确认于
2024/07/09 15:25
2 年前
查看原帖
下两代码中均有
CPP
n=strlen(p+1);
这一语句,但在最后输出的时候
CPP
for(int i=1;i<=n;i++)
CPP
for(int i=1;i<=strlrn(p+1);i++)
输出效果是时间上的差异
代码1(subtask3TLE)
CPP
#include<iostream>
#include<string.h>
using namespace std;
const int mx=1e6+10;
char t[mx],p[mx];
int nxt[mx],n,m;
int main() {
	scanf("%s%s",t+1,p+1);
	n=strlen(p+1), m=strlen(t+1);
	nxt[1]=0;
	for(int i=2,k=0;i<=n;i++){
		while(k&&p[i]!=p[k+1]) k=nxt[k]; 
		if(p[i]==p[k+1]) k++;
		nxt[i]=k;
	}
	for(int i=1,k=0;i<=m;i++){
		while(k&&t[i]!=p[k+1]) k=nxt[k];
		if(t[i]==p[k+1]) k++;
		if(k==n) printf("%d\n",i-k+1), k=nxt[k];
	}
	for(int i=1;i<=strlen(p+1);i++)printf("%d ",nxt[i]);
	return 0;
}
code 2(AC)
CPP
#include<iostream>
#include<string.h>
using namespace std;
const int mx=1e6+10;
char t[mx],p[mx];
int nxt[mx],n,m;
int main() {
	scanf("%s%s",t+1,p+1);
	n=strlen(p+1), m=strlen(t+1);
	nxt[1]=0;
	for(int i=2,k=0;i<=n;i++){
		while(k&&p[i]!=p[k+1]) k=nxt[k]; 
		if(p[i]==p[k+1]) k++;
		nxt[i]=k;
	}
	for(int i=1,k=0;i<=m;i++){
		while(k&&t[i]!=p[k+1]) k=nxt[k];
		if(t[i]==p[k+1]) k++;
		if(k==n) printf("%d\n",i-k+1), k=nxt[k];
	}
	for(int i=1;i<=n;i++)printf("%d ",nxt[i]);
	return 0;
}

回复

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

正在加载回复...