제출 #1303720

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

necklace

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mt make_tuple
#define mp make_pair
#define all(x) (x).begin(), (x).end()

const int N = 6000 + 10;
const int LG = 20;
const int INF = 1e9 + 10;
const ll LL_INF = 1e18 + 10;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 998244353;

tuple <int, int, char> moves[4] {
    {0, 1, 'R'}, {1, 0, 'D'}, {0, -1, 'L'}, {-1, 0, 'U'}
};

string S, T;
int p1[N], p2[N];

void find_kmp(string s, int *p) {
    p[0] = 0;
    int n = s.size();
    for (int i = 1; i < n; i++) {
        int j = p[i - 1];
        while (j && s[j] != s[i]) {
            j = p[j - 1];
        }
        if (s[j] == s[i]) j++;
        p[i] = j;
    }
}

tuple <int, int, int> find_ans(string s, string t, bool rev) {
    tuple <int, int, int> ans = {-1, 0, 0};
    int n = s.size(), m = t.size();
    for (int i = 0; i < n; i++) {
        string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
        reverse(all(s1));
        string t1 = t, t2 = t;
        reverse(all(t2));
        find_kmp(s1 + '#' + t1, p1);
        find_kmp(s2 + '#' + t2, p2);
        for (int j = 1; j <= m; j++) {
            ans = max(ans, {p1[i + j] + p2[n + m - i - j], i - p1[i + j], rev ? m - j - p2[n + m - i - j] : j - p1[i + j]});
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> S >> T;
    tuple <int, int, int> ans = {-1, 0, 0};
    ans = max(ans, find_ans(S, T, 0));
    reverse(all(T));
    ans = max(ans, find_ans(S, T, 1));
    {
        auto [a, b, c] = ans;
        cout << a << '\n' << b << ' ' << c << '\n';
    }
    return 0;
}

• Subtask 1: 15 / 15