Submission #754807

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754807	2023-06-08T15:46:17 Z	vjudge1	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	327 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	291 ms	436 KB	Output is correct
2	Correct	240 ms	468 KB	Output is correct
3	Correct	327 ms	504 KB	Output is correct
4	Correct	229 ms	428 KB	Output is correct
5	Correct	134 ms	436 KB	Output is correct
6	Correct	146 ms	428 KB	Output is correct
7	Correct	194 ms	440 KB	Output is correct
8	Correct	228 ms	524 KB	Output is correct
9	Correct	270 ms	436 KB	Output is correct