社区讨论
求救
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 条回复,欢迎继续交流。
正在加载回复...