感觉写得没有问题但一交上去就RE,求助。
ps:Dev坏了现在只能用洛谷IDE调试,洛谷IDE上测的没问题,输出也是对的,不知道怎么回事。
代码如下:
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int nextt[1000005];
void Knext(){
nextt[0]=-1;
int i=0,j=-1;
while(i<s2.length()){
if(j==-1||s2[j]==s2[i]){
i++;
j++;
nextt[i]=j;
}
else{
j=nextt[j];
}
}
}//求next数组
void KMPfind(){
int i=0,j=0;
int len1=s1.length(),len2=s2.length();
while(i<len1){
while(j<len2){
if(j==-1||s1[i]==s2[j]){
i++;
j++;
}
else{
j=nextt[j];
}
}
j=0;
if(i<len1)cout<<i-len2+1<<endl;
i=i-len2+2;
}
}//KMP查找部分
int main(){
cin>>s1>>s2;
Knext();
KMPfind();
for(int i=1;i<=s2.length();i++){
cout<<nextt[i]<<" ";
}
return 0;
}