Submission #388825

#	Time	Username	Problem	Language	Result	Execution time	Memory
388825		ngpin04	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	502 ms	712 KiB

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 / 15