蒟蒻求助,悬关,样例过了,luogu全RE!
看了几个讨论版里面的RE的,也没有解决问题
求助大佬!
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define CLOSE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define isd(c) ('0' <= (c) && (c) <= '9')
#define isa(c) ('a' <= (c) && (c) <= 'z')
#define isA(c) ('A' <= (c) && (c) <= 'Z')
#define mem(a, b) memset(a, b, sizeof a);
#define N 2005
#define M 4000005
#define mod 998244353
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define PI acos(-1)
#define endl "\n"
#define pii pair<int, int>
#define F first
#define S second
#define bug cout << endl << " .....here!...." << endl;
//#define s1 sss
//#define s2 ssss
//#define next nnext
#define int long long
//#pragma GCC optimize("O3")
using namespace std;
int len1,len2;
//string s1,s2;
char s1[1000010],s2[1000010];
int nnext[1000010];
void makenext(){
nnext[0]=0;
int cnt=1;
int i=1;
int pos=0;
while(i<len2){
if(s2[pos]==s2[i]){
pos++;
nnext[cnt]=pos;
cnt++;
i++;
}
else{
if(pos==0){
i++;
nnext[cnt]=0;
cnt++;
}
else{
pos=nnext[pos-1];
}
}
}
return ;
}
int kmp(int x){
int i=x;
int j=0;
while(i<len1){
if(s1[i]==s2[j]){
i++;
j++;
}
else if(j>0){
j=nnext[j-1];
}
else{
i++;
}
if(j==len2){
return i-j;
}
}
}
signed main(){
// cin>>s1>>s2;
scanf("%s%s",&s1,&s2);
len1=strlen(s1);
len2=strlen(s2);
makenext();/*int i;*/
for(int i=0;i<=len1;i++){
i=kmp(i);
i++;
if(i<=len1-1){
cout<<i<<endl;
}
}
for(int i=0;i<=len2-1;i++){
cout<<nnext[i]<<" ";
}
return 0;
}
//效率是代码的事,优雅是一辈子的事w~
下载了第一个测试点也本地过了