oj.uz

Submission #775710

# Submission time Handle Problem Language Result Execution time Memory
775710 2023-07-06T19:32:36 Z beaboss Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 191 ms 536 KB 
// Source: https://oj.uz/problem/view/BOI19_necklace4

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

int p1[6005];
int p2[6005];

void get_kmp(string s, int *pi_s) {
	int n = (int)s.size();

	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[j] != s[i]) { j = pi_s[j - 1]; } // next smallest prefix that is also a suffix
		if (s[i] == s[j]) { j++; }
		pi_s[i] = j;
	}
}

pair<int, pii> solve(string s, string t, bool rev) {
	int n = s.size();
	int m = t.size();

	string t_rev = t;

	reverse(t_rev.begin(), t_rev.end());

	pair<int, pii> ans;

	for (int i = 0; i < n; i++) {

		string s1 = s.substr(0, i);
		string s2 = s.substr(i, n - i);

		reverse(s1.begin(), s1.end());

		get_kmp(s1 + "$" + t, p1);
		get_kmp(s2 + "$" + t_rev, p2);

		for (int j = 1; j <= m; j++) {
			ans = max(ans, {p1[i + j] + p2[n - i + m - j], {i - p1[i + j], rev ? m - j - p2[n - i + m - j] : j - p1[i + j]}});
		}

	}

	return ans;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string a, b;
	cin >> a >> b;

	auto ans = solve(a, b, false);
	reverse(b.begin(), b.end());

	ans = max(ans, solve(a, b, true));
	cout << ans.f << '\n' << ans.s.f << ' ' << ans.s.s << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 436 KB Output is correct
2 Correct 151 ms 460 KB Output is correct
3 Correct 191 ms 460 KB Output is correct
4 Correct 133 ms 452 KB Output is correct
5 Correct 140 ms 460 KB Output is correct
6 Correct 163 ms 536 KB Output is correct
7 Correct 167 ms 460 KB Output is correct
8 Correct 163 ms 460 KB Output is correct
9 Correct 175 ms 460 KB Output is correct