社区讨论
没看出来哪里错了
P3375【模板】KMP参与者 5已保存回复 12
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 12 条
- 当前快照
- 1 份
- 快照标识符
- @lo3axjfz
- 此快照首次捕获于
- 2023/10/24 03:39 2 年前
- 此快照最后确认于
- 2023/10/24 03:39 2 年前

0分,有点头秃
但是输出结果明明看起来一模一样
下面是代码,感觉好像没什么问题
CPP#include <iostream>
#include <string>
#include <vector>
int tsize, ssize;
std::vector<int> mynext;
void getNext(std::string &t){
mynext.resize(tsize);
mynext[0]=0;
for(int i=1; i<tsize; i++){
int k=mynext[i-1];
while((t[i] != t[k]) && (k!=0))k=mynext[k-1];
if(t[i] == t[k])mynext[i]=k+1;
else mynext[i]=0;
}
}
inline void output(int i){
printf("%d\n",i+1);
}
int cnt;
void kmp(std::string &s, std::string &t, int startpos){
int i = startpos, j = 0;
ssize = s.size(), tsize = t.size();
getNext(t);
while(s[i]!=t[0]){i++;}
int icopy = i;
while(i+tsize<=ssize){
//std::cout<<"this is a test: "<<cnt++<<std::endl
// <<"i= "<<i<<" "<<"j= "<<j<<std::endl;
while(s[i]!=t[0]){i++; icopy=i;}
if(s[icopy]==t[j]){
icopy++, j++;
if(j==tsize){
output(i);
//if(!(j-1) || !(j-mynext[j-1]))return;
i += j-mynext[j-1];
icopy = i; j = 0;
}
}
else{
//if(!(j-1) || !(j-mynext[j-1]))return;
i += j-mynext[j-1];
icopy = i; j = 0;
}
}
}
int main(){
std::string s, t;
getline(std::cin,s);
getline(std::cin,t);
kmp(s, t, 0);
//std::cout<<"this is a test."<<std::endl;
for(auto i = mynext.begin(); i != mynext.end(); i++){
std::cout<<*i<<" ";
}
std::cout<<std::endl;
return 0;
}
// agctagcagctagct
/*
aba
a
this is a test: 0
i= 0 j= 0
1
this is a test: 1
i= 1 j= 0
this is a test: 2
i= -469795857 j= 0
*/
回复
共 12 条回复,欢迎继续交流。
正在加载回复...