KMP板子错了 求助
查看原帖
KMP板子错了 求助
608251
zfznbnb楼主2023/1/10 09:16

感觉写得没有问题但一交上去就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;
}
2023/1/10 09:16
加载中...