Submission #754806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754806	2023-06-08T15:46:02 Z	adaawf	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	329 ms	524 KB

necklace

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kmp(string s) {
	int n = s.size();
	vector<int> k(n);
	for (int i = 1; i < n; i++) {
		int j = k[i - 1];
		while (j != 0 && s[i] != s[j]) {
            j = k[j - 1];
		}
		if (s[i] == s[j]) {
            j++;
		}
		k[i] = j;
	}
	return k;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size(), ma = 0;
	pair<int, int> p;
	for (int i = 0; i < n; i++) {
		string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
		reverse(h.begin(), h.end());
		reverse(g.begin(), g.end());
		vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
		for (int j = 1; j <= m; j++) {
			int h = v[i + j] + vv[n + m - i - j];
			if (ma < h) {
				ma = h;
				p = {i - v[i + j], j - v[i + j]};
			}
		}
	}
	reverse(t.begin(), t.end());
	for (int i = 0; i < n; i++) {
		string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
		reverse(h.begin(), h.end());
		reverse(g.begin(), g.end());
		vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
		for (int j = 1; j <= m; j++) {
			int h = v[i + j] + vv[n + m - i - j];
			if (ma < h) {
				ma = h;
				p = {i - v[i + j], m - j - vv[n + m - i - j]};
			}
		}
	}
	cout << ma << endl;
	cout << p.first << ' ' << p.second;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	444 KB	Output is correct
2	Correct	232 ms	444 KB	Output is correct
3	Correct	329 ms	440 KB	Output is correct
4	Correct	230 ms	324 KB	Output is correct
5	Correct	132 ms	340 KB	Output is correct
6	Correct	145 ms	436 KB	Output is correct
7	Correct	205 ms	524 KB	Output is correct
8	Correct	235 ms	396 KB	Output is correct
9	Correct	249 ms	444 KB	Output is correct