Submission #470015

#	Time	Username	Problem	Language	Result	Execution time	Memory
470015		naman1601	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	374 ms	520 KiB

necklace

// time-limit: 3000
/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


void kmp(vector<int>& v, int len, string s) {

	fr(i, 1, len) {

		int j = v[i - 1];

		while(j > 0 && s[i] != s[j]) {

			j = v[j - 1];
		}

		if(s[i] == s[j]) {

			j++;
		}
		
		v[i] = j;
	}
}


string s, t;
int sl, tl;
int ans = 0;
pii ap = make_pair(-1, -1);


void f() {

	fr(i, 1, sl + 1) {

		string first_half = s.substr(0, i);
		string second_half = s.substr(i, s.length() - i);
		string t_prime = t;
		reverse(first_half.begin(), first_half.end());
		reverse(t_prime.begin(), t_prime.end());

		string aux = second_half + t;
		string aux_prime = first_half + t_prime;
		int auxl = aux.length();
		int aux_primel = aux_prime.length();

		vector<int> pf(auxl, 0), pf_prime(aux_primel, 0);
		kmp(pf, auxl, aux);
		kmp(pf_prime, aux_primel, aux_prime);

		fr(j, 1, tl + 1) {

			int temp = pf[second_half.length() + j] + pf_prime[first_half.length() + t.length() - (j + 1) - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(i - pf_prime[first_half.length() + t.length() - (j + 1) - 1], j - pf[second_half.length() + j] + 1);
			}
		}
	}
}


void g() {

	fr(i, 1, sl + 1) {

		string first_half = s.substr(0, i);
		string second_half = s.substr(i, s.length() - i);
		string t_prime = t;
		reverse(first_half.begin(), first_half.end());
		reverse(t_prime.begin(), t_prime.end());

		string aux = second_half + t;
		string aux_prime = first_half + t_prime;
		int auxl = aux.length();
		int aux_primel = aux_prime.length();

		vector<int> pf(auxl, 0), pf_prime(aux_primel, 0);
		kmp(pf, auxl, aux);
		kmp(pf_prime, aux_primel, aux_prime);

		fr(j, 1, tl + 1) {

			int temp = pf[second_half.length() + j] + pf_prime[first_half.length() + t.length() - (j + 1) - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(s.length() - (i + pf[second_half.length() + j] - 1) - 1, j - pf[second_half.length() + j] + 1);
			}
		}
	}
}


void solve() {

	cin >> s >> t;
	sl = s.length();
	tl = t.length();
	s = "(" + s + ")";
	t = "[" + t + "]";
	f();
	reverse(s.begin(), s.end());
	g();
	cout << ans << "\n" << ap.fe - 1 << " " << ap.se - 1 << nl;
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

• Subtask 1: 15 / 15