Submission #869231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869231	2023-11-03T15:38:30 Z	Calico	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	203 ms	520 KB

necklace

#include <bits/stdc++.h>
using namespace std;

/*
	|--- S1 S2 ---|
	|--- T2 T1 ---|

	(T1 = S1, T2 = S2)

	Iterate through T-cut

	forward KMP through T1, backward KMP through T2
*/

vector<int> pi(const string& s) {
	vector<int> p(s.size());
	for (int i = 1; i < (int)s.size(); i++) {
		int g = p[i-1];
		while (g && s[i] != s[g]) g = p[g-1];
		p[i] = g + (s[i] == s[g]);
	}
	return p;
}

// finds the longest necklace, no reversal
tuple<int, int, int> solve(string &s, string &t) {
	int n = s.size(), m = t.size();

	int l = 0, a = 0, b = 0;
	for (int cut = 0; cut < m; cut++) {
		// T1 = [0, cut), T2 = [cut, m)

		vector<int> fBord(n), bBord(n); // S1, S2

		{ // forward kmp (T1)
			string s2 = t.substr(cut, m-cut);
			vector<int> kmp = pi(s2);

			int cur = 0;
			for (int i = 0; i < n; i++) {
				while (cur != 0 && s[i] != s2[cur]) {
					cur = kmp[cur-1];
				}
				if (s[i] == s2[cur]) {
					cur++;
				}
				fBord[i] = cur;
				if (cur == (int)s2.size()) {
					cur = kmp[cur-1];
				}
			}
		}

		if (cut > 0) { // backwards kmp (T2)
			string s2 = t.substr(0, cut);
			reverse(s2.begin(), s2.end());
			vector<int> kmp = pi(s2);

			int cur = 0;
			for (int i = n-1; i >= 0; i--) {
				while (cur != 0 && s[i] != s2[cur]) {
					cur = kmp[cur-1];
				}
				if (s[i] == s2[cur]) {
					cur++;
				}
				bBord[i] = cur;
				if (cur == (int)s2.size()) {
					cur = kmp[cur-1];
				}
			}
		}

		// find optimal cut position
		for (int i = 0; i < n; i++) {
			int mxlen = bBord[i];
			if (i > 0) mxlen += fBord[i-1];

			if (mxlen > l) {
				l = mxlen;
				a = (i > 0 ? i-fBord[i-1] : 0);
				b = cut - bBord[i];
			}
		}
	}

	return {l, a, b};
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);

	string s, t; cin >> s >> t;
	int /*n = s.size(),*/ m = t.size();

	auto [l1, a1, b1] = solve(s, t);
	reverse(t.begin(), t.end());
	auto [l2, a2, b2] = solve(s, t); 
	b2 = m-(b2+l2-1)-1;

	if (l1 > l2) {
		cout << l1 << '\n' << a1 << ' ' << b1 << '\n';
	} else {
		cout << l2 << '\n' << a2 << ' ' << b2 << '\n';
	}

	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	520 KB	Output is correct
2	Correct	144 ms	520 KB	Output is correct
3	Correct	203 ms	344 KB	Output is correct
4	Correct	133 ms	516 KB	Output is correct
5	Correct	101 ms	520 KB	Output is correct
6	Correct	117 ms	516 KB	Output is correct
7	Correct	130 ms	512 KB	Output is correct
8	Correct	154 ms	344 KB	Output is correct
9	Correct	161 ms	348 KB	Output is correct