제출 #1183737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183737		NK_	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	218 ms	576 KiB

necklace

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back

using str = string;
template<class T> using V = vector<T>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	str S, T; cin >> S >> T;

	str RT = T; reverse(begin(RT), end(RT));

	int N = sz(S), M = sz(T);

	auto kmp = [&](str s) {
		int n = sz(s); vi len(n);
		for(int i = 1; i < n; i++) {
			int j = len[i - 1];
			while(j && s[i] != s[j]) j = len[j - 1];
			if (s[i] == s[j]) j++;
			len[i] = j;
		}
		return len;
	};

	int ans = 0, l1 = -1, l2 = -1;
	for(int t = 0; t < 2; t++) {
		
		for(int i = 0; i < N; i++) {
			str p = S.substr(0, i); str s = S.substr(i);
			reverse(begin(p), end(p));

			vi r = kmp(s + "#" + T), l = kmp(p + "#" + RT);
			// cout << p + "#" + RT << " " << s + "#" + T << endl;

			for(int j = 0; j < M; j++) {
				int jl = sz(p) + M - 1 - j, jr = sz(s) + j + 1;
				// cout << i << " " << j << " => " << l[jl] << " " << r[jr] << endl;
				if (ans < l[jl] + r[jr]) {
					ans = l[jl] + r[jr];
					l1 = i - l[jl];
					if (!t) l2 = j + 1 - r[jr];
					if (t) l2 = M - 1 - j - l[jl];
					// cout << ans << " " << l1 << " " << l2 << endl;
				}
			}
		}

		T.swap(RT);
	}

	cout << ans << nl;
	cout << l1 << " " << l2 << nl;


	exit(0-0);
}

// abcde def
// def abcde

// Breathe In, Breathe Out

• Subtask 1: 15 / 15