全RE
查看原帖
全RE
115067
Adis_FireDevil楼主2021/7/6 17:55

在线IDE和c++上运行结果都没问题,交到luogu上全re

码(可能有点丑

#include<bits/stdc++.h>
using namespace std;
char a[1000011],s[1000011];
int next[1000011],n,m;
void gnext(){
	int q=0;
	for(int i=2;i<=n;i++){
		while(s[q+1]!=s[i]&&q>0){q=next[q];}
		if(s[q+1]==s[i])q++;
		next[i]=q;
	}
}
int kmp() {
	int j=0;
	for(int i=1;i<=m;i++){
		while(j>0&&s[j+1]!=a[i])j=next[j];
		if(s[j+1]==a[i])j++;
		if(j==n){
			cout<<i+1-n<<endl;
			j=next[j];
		}
	}
}
int main() {
	scanf("%s%s",a+1,s+1);
	m=strlen(a+1);
	n=strlen(s+1);
	gnext();
	kmp();
	for(int i=1; i<=n; i++)cout<<next[i]<<" ";
	return 0;
}

1.in

CEBDAEEAACEBDAE
EBDAE

1.out

2
11
0 0 0 0 1 

2021/7/6 17:55
加载中...