求助,爆灵,但数据下载是对的
查看原帖
求助,爆灵,但数据下载是对的
543206
shiroko2008楼主2022/4/30 14:25
#include<bits/stdc++.h>
using namespace std;
vector<int> prefix(string s) {
	int n=s.length();
	vector<int> pi(n);
	pi[0]=0;
	for (int i=1;i<n;i++) {
		int j=pi[i-1];
		while (j>0&&s[i]!=s[j]) j=pi[j-1];
		if(s[i]==s[j]) j++;
		pi[i]=j;
	}
	return pi;
}
int main() {
	string s1,s2;
	cin>>s1>>s2;
	int l1=s1.length(),l2=s2.length();
	string s=s2+"€"+s1;
	vector<int> v=prefix(s);
	int len=s.length();
	//for (int i=0;i<len;i++) cout<<v[i]<<' ';
	for (int i=l2;i<len;i++) if(v[i]==l2) cout<<(i-l2-l2+1)<<endl;
	for (int i=0;i<l2;i++) cout<<v[i]<<' ';
	return 0;
}
2022/4/30 14:25
加载中...