Submission #388825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
388825	2021-04-13T05:35:00 Z	ngpin04	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	502 ms	712 KB

necklace

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 3e3; 

string s,t;

int n,m;

vector <int> KMP(string s, string t) {
	string str = s + '#' + t;
	vector <int> kmp(str.size());
	for (int i = 1; i < (int) str.size(); i++) {
		int &res = kmp[i];
		res = kmp[i - 1];
		while (res > 0 && str[res] != str[i])
			res = kmp[res - 1];
		res += str[res] == str[i];
	}
	reverse(kmp.begin(), kmp.end());
	while (kmp.size() > t.size())
		kmp.pop_back();
	reverse(kmp.begin(), kmp.end());
	return kmp;
}

pair <int, pair <int, int>> solve(string s, string t) {
	string invt = t;
	reverse(invt.begin(), invt.end());
	
	int ans = 0;
	pair <int, int> pos = mp(0, 0);	
	for (int mid = 0; mid < n; mid++) {
		vector <int> f = KMP(s.substr(mid + 1), t);

		string invs = s.substr(0, mid + 1);
		reverse(invs.begin(), invs.end());
		vector <int> g = KMP(invs, invt);
		reverse(g.begin(), g.end());

		g.push_back(0);
		for (int j = 0; j < m; j++) {
			if (ans < f[j] + g[j + 1]) {
				ans = f[j] + g[j + 1];
				pos.fi = mid - g[j + 1] + 1;
				pos.se = j - f[j] + 1;
			}
		}
	}
	return mp(ans, pos);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> t;
	n = s.size();
	m = t.size();
	auto ans = solve(s, t);
	reverse(t.begin(), t.end());
	auto tmp = solve(s, t);
	if (tmp.fi > ans.fi) {
		ans = tmp;
		ans.se.se = m - ans.se.se - 1;
		ans.se.se -= ans.fi - 1;
	}
	cout << ans.fi << "\n" << ans.se.fi << " " << ans.se.se;
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	486 ms	488 KB	Output is correct
2	Correct	423 ms	400 KB	Output is correct
3	Correct	473 ms	712 KB	Output is correct
4	Correct	367 ms	484 KB	Output is correct
5	Correct	447 ms	560 KB	Output is correct
6	Correct	502 ms	592 KB	Output is correct
7	Correct	450 ms	488 KB	Output is correct
8	Correct	454 ms	612 KB	Output is correct
9	Correct	463 ms	480 KB	Output is correct