社区讨论
赋值问题
P3375【模板】KMP参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lye125md
- 此快照首次捕获于
- 2024/07/09 14:25 2 年前
- 此快照最后确认于
- 2024/07/09 15:25 2 年前
下两代码中均有
CPPn=strlen(p+1);
这一语句,但在最后输出的时候
CPPfor(int i=1;i<=n;i++)
与
CPPfor(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 条回复,欢迎继续交流。
正在加载回复...