蒟蒻求助,悬关,样例过了,luogu全RE
查看原帖
蒟蒻求助,悬关,样例过了,luogu全RE
309158
Happy_King楼主2023/11/13 18:15

蒟蒻求助,悬关,样例过了,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~ 

下载了第一个测试点也本地过了

2023/11/13 18:15
加载中...