제출 #1187136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187136		tamyte	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	208 ms	632 KiB

necklace

#include <bits/stdc++.h>


using namespace std;

void prepare(string s, vector<int>& p) {
	p = vector<int>(s.size());
	for (int i = 1, j = 0; i < (int)s.size(); ++i) {
		while (j != 0 && s[i] != s[j]) {
			j = p[j - 1];
		}
		if (s[i] == s[j]) j++;
		p[i] = j;
	}
}

array<int, 3> solve(string& s, string& t, bool revers) {
	int n = s.size();
	int m = t.size();
	vector<int> p1, p2;
	array<int, 3> res = {0, 0, 0};
	for (int i = 0; i < n; ++i) {
		string s1 = s.substr(0, i);
		string s2 = s.substr(i);
		reverse(begin(s1), end(s1));
		string t1 = t, t2 = t;
		reverse(begin(t2), end(t2));
		prepare(s1 + "#" + t1, p1);
		prepare(s2 + "#" + t2, p2);
		for (int j = 1; j <= m; ++j) {
			array<int, 3> now;
			now[0] = p1[i + j] + p2[n + m - i - j];
			now[1] = i - p1[i + j];
			now[2] = (revers ? m - j - p2[n + m - i - j] : j - p1[i + j]);
			res = max(res, now);
		}
	}
	return res;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s,t ;
	cin >> s >> t;
	array<int, 3> res = solve(s, t, false);
	reverse(begin(t), end(t));
	res = max(res, solve(s, t, true));
	cout << res[0] << "\n";
	cout << res[1] << " " << res[2] << "\n";
}

• Subtask 1: 15 / 15