제출 #1355761

#제출 시각아이디문제언어결과실행 시간메모리
1355761CutSandstoneNecklace (Subtask 4) (BOI19_necklace4)C++20
15 / 15
233 ms512 KiB
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
using ll = long long;
vector<int> pi(const string& s) {
	int n = (int)s.size();
	vector<int> pi_s(n);
	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[j] != s[i]) {
			j = pi_s[j - 1];
		}
		if (s[i] == s[j]) {
			j++;
		}
		pi_s[i] = j;
	}
	return pi_s;
}
vector<int> calc(string s, string t) {
	vector<int> ret(s.size());
	string cur = t + "#" + s;
	vector<int> p = pi(cur);
	for (int i = 0; i < s.size(); i++) ret[i] = p[i + t.size() + 1];
	return ret;
}
pair<int, pair<int, int>> solve(string s, string t) {
	t += ".";
	pair<int, pair<int, int>> ans = {0, {0, 0}};
	for (int i = 0; i < t.size() - 1; i++) {
		vector<int> left = calc(s, t);
		reverse(s.begin(), s.end());
		reverse(t.begin(), t.end());
		vector<int> right = calc(s, t);
		reverse(s.begin(), s.end());
		reverse(t.begin(), t.end());
		reverse(right.begin(), right.end());
		for (int j = 0; j <= s.size(); j++) {
			int l = j == 0 ? 0 : left[j - 1];
			int r = j == s.size() ? 0 : right[j];
			ans = max(ans,
					  {l + r,
					   {j - l, (2 * (t.size() - 1) - r + i) % (t.size() - 1)}});
		}
		rotate(t.begin(), t.begin() + 1, t.end());
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s, t;
	cin >> s >> t;
	pair<int, pair<int, int>> ans = solve(s, t);
	reverse(t.begin(), t.end());
	pair<int, pair<int, int>> cur = solve(s, t);
	cur.b.b = t.size() - cur.b.b - cur.a;
	ans = max(ans, cur);
	cout << ans.a << "\n";
	if (ans.a) cout << ans.b.a << " " << ans.b.b << "\n";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…