社区讨论

没看出来哪里错了

P3375【模板】KMP参与者 5已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@lo3axjfz
此快照首次捕获于
2023/10/24 03:39
2 年前
此快照最后确认于
2023/10/24 03:39
2 年前
查看原帖
数据是洛谷的数据点1
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 条回复,欢迎继续交流。

正在加载回复...