22pt求助大佬!!!
查看原帖
22pt求助大佬!!!
389982
LiuzihanAC楼主2023/11/12 21:41
#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<int> exkmp(string s,int m) {
	int n = (int)s.size();
	s = "#" + s;
	vector<int> z(n + 1);
	int L = 1, R = 0;
	for (int i = 2; i <= n; i++) {
		if (i > R) {
			z[i] = 0;
		}
		else {
			z[i] = min(z[i - L + 1], R - i + 1);
		}
		while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) {
			z[i]++;
		}
		if (i + z[i] - 1 > R) {
			L = i;
			R = i + z[i] - 1;
		}
	}
	z[1] = m;
	return z;
}

int main() {
	string s;
	cin >> s;
	string t;
	cin >> t;
	s = t + "#" + s;
	vector<int> ans = exkmp(s,t.size());
	unsigned long long a = 0;
	int j = 1;
	for (int i = 1; i <= t.size(); i++) {
		a ^= ((ans[i]+1) * (j));
		j++;
	}
	cout << a << endl;
	unsigned long long b = 0;
	j = 1;
	for (int i = t.size() + 2; i < ans.size(); i++) {
		b ^= ((ans[i]+1) * (j));
		j++;
	}
	cout << b;
}

2023/11/12 21:41
加载中...