Submission #319916

#	Time	Username	Problem	Language	Result	Execution time	Memory
319916		kostia244	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	299 ms	612 KiB

necklace

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 3030;
int pref[maxn], suf[maxn];
array<int, 3> solve(string s, string t, int rev = 0) {
	int n = s.size();
	int ans = 0;
	int P1 = 0, P2 = 0;
	//cout << s << " " << t << endl;
	for(int cut = 0; cut < n; cut++) {
		memset(pref, 0, sizeof pref);
		memset(suf, 0, sizeof suf);
		vector<int> b{-1};
		for(int i = 0, j = -1; cut+i < n; i++) {
			while(j != -1 && s[cut+i] != s[cut+j]) j = b[j];
			j++;
			b.push_back(j);
		}
		for(int i = 0, j = 0; i < t.size(); i++) {
			while(j != -1 && t[i] != s[cut+j]) j = b[j];
			pref[i] = ++j;
			if(j+1 == b.size()) j = b.back();
		}
		if(cut) {
			cut--;
			vector<int> b{-1};
			for(int i = 0, j = -1; cut-i >= 0; i++) {
				while(j != -1 && s[cut-i] != s[cut-j]) j = b[j];
				j++;
				b.push_back(j);
			}
			for(int i = t.size(), j = 0; i--;) {
				while(j != -1 && t[i] != s[cut-j]) j = b[j];
				suf[i] = ++j;
				if(j+1 == b.size()) j = b.back();
			}
			cut++;
		}
		//cout << cut << ":\n";
		//for(int i = 0; i < t.size(); i++) cout << pref[i] << " "; cout << endl;
		//for(int i = 0; i < t.size(); i++) cout << suf[i] << " "; cout << endl;
		for(int i = 0; i < t.size(); i++) {
			if(ans < pref[i] + suf[i+1]) {
				ans = pref[i]+suf[i+1];
				P1 = cut-suf[i+1];
				P2 = i+1-pref[i];
				if(rev) P2 = t.size()-P2-ans;
				//if(ans == 5) cout << cut << " " << i << " " << pref[i] << " " << suf[i+1] << endl;
			}
		}
	}
	return {ans, P1, P2};
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	string x, y;
	cin >> x >> y;
	auto ans = solve(x, y);
	reverse(all(y));
	ans = max(ans, solve(x, y, 1));
	cout << ans[0] << '\n' << ans[1] << " " << ans[2] << '\n';
}

Compilation message (stderr)

necklace.cpp: In function 'std::array<int, 3> solve(std::string, std::string, int)':
necklace.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i = 0, j = 0; i < t.size(); i++) {
      |                         ~~^~~~~~~~~~
necklace.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    if(j+1 == b.size()) j = b.back();
      |       ~~~~^~~~~~~~~~~
necklace.cpp:36:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(j+1 == b.size()) j = b.back();
      |        ~~~~^~~~~~~~~~~
necklace.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i = 0; i < t.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 15 / 15