제출 #1335935

#제출 시각아이디문제언어결과실행 시간메모리
1335935lanternerNecklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
237 ms584 KiB
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
#define iii int, int ,int
#define tp tuple

using namespace std;
const ll maxN = 6005;

string s, t;
int n, m, pi[maxN][2];

void kmp (string s, int side) {
	int n = s.size()-1;
	fto (i, 1, n, 1) {
		int j = pi[i-1][side];
		while (0 < j && s[i] != s[j]) j = pi[j - 1][side];
		if (s[i] == s[j]) j++;
		pi[i][side] = j;
	}
}

tp<iii> solve(string s, string t, int side) {
	n = s.size()-1, m = t.size()-1;
	tp<iii> ans = make_tuple(0, 0, 0);
	reverse(all(t));
	string rev = t;
	reverse(all(t));	
	fto (i, 0, n, 1) {
		string s1 = s.substr(0, i+1), s2 = s.substr(i+1, n - i);
		reverse(all(s1));
		int n1 = s1.size(), n2 = s2.size();
		s1 = s1 + "#" + rev;
		s2 = s2 + "#" + t;
		kmp(s1, 0); kmp(s2, 1);
		fto (j, -1, m, 1) {
			int pos = j - pi[n2+1+j][1] + 1;
			ans = max(ans, make_tuple(pi[n2+1+j][1] + pi[n1+m-j][0], 
									  i - pi[n1+m-j][0] + 1,
									  (side ? pos : m - (j + pi[n2+1+j][1]))));
		}
		/*if (i == 2) {
			fto (j, 0, s2.size()-1, 1) {
				cout << s2[j] << ' ' << pi[j][1] << '\n';
			}
		}*/
	}
	return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s >> t;
    tp<iii> ans = solve(s, t, 1);
    reverse(all(t));
    ans = max(ans, solve(s, t, 0));
    cout << get<0>(ans) << '\n';
    cout << get<1>(ans) << ' ' << get<2>(ans) << '\n';
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...