Submission #469904

#	Time	Username	Problem	Language	Result	Execution time	Memory
469904		naman1601	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	180 ms	65540 KiB

necklace

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#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, string s, int len) {

	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;
	}
}


const int maxn = 3005;
string s, t;
int sl, tl;
int stdp[maxn][maxn] = {0};
int tsdp[maxn][maxn] = {0};


int ans = 0;
pii ap = make_pair(-1, -1);


int inv(int idx) {

	return (sl - idx) - 1;
}


void pc() {

	fr(i, 0, sl) {

		string aux = s.substr(i, sl - i) + "#" + t;
		int al = aux.length();
		vector<int> pf(al, 0);
		kmp(pf, aux, al);

		fr(j, 0, tl) {

			stdp[i][j] = pf[al - tl + j];
		}
	}

	fr(i, 0, tl) {

		string aux = t.substr(i, tl - i) + "#" + s;
		int al = aux.length();
		vector<int> pf(al, 0);
		kmp(pf, aux, al);

		fr(j, 0, sl) {

			tsdp[i][j] = pf[al - sl + j];
		}
	}
}


void f() {

	fr(i, 0, 1) {

		fr(j, 0, tl) {

			int temp = stdp[i][j];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(0, j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}

	fr(i, 1, sl) {

		fr(j, 0, tl) {

			int temp = stdp[i][j] + tsdp[j + 1][i - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair((i - 1) - tsdp[j + 1][i - 1] + 1, j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}
}


void g() {

	fr(i, 0, 1) {

		fr(j, 0, tl) {

			int temp = stdp[i][j];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(inv(stdp[i][j] - 1), j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}

	fr(i, 1, sl) {

		fr(j, 0, tl) {

			int temp = stdp[i][j] + tsdp[j + 1][i - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(inv(i + stdp[i][j] - 1), j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}
}


void solve() {

	cin >> s >> t;
	sl = s.length();
	tl = t.length();

	pc();

	// fr(i, 0, sl) {

	// 	fr(j, 0, tl) {

	// 		cout << i << ", " << j << ": " << stdp[i][j] << nl;
	// 	}
	// }

	f();
	reverse(s.begin(), s.end());
	pc();
	g();

	// fr(i, 0, sl) {

	// 	fr(j, 0, tl) {

	// 		cout << i << ", " << j << ": " << stdp[i][j] << nl;
	// 	}
	// }

	cout << ans << nl << ap.fe << " " << ap.se << nl;
}


int main() {
	
	speed;

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

	while(q-- > 0) {

		solve();
	}

	return 0;
}

• Subtask 1: 0 / 15