Submission #1168890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168890		htphong0909	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	191 ms	520 KiB

necklace

#include<bits/stdc++.h>
//#define int short
#define sz(x) static_cast<int>(x.size())
using namespace std;

string S, T;
int N, M;
array<int, 3> ans;

vector<int> match(const string& s, const string& t) {
    const int n = sz(s) - 1;
    const int m = sz(t) - 1;
    if (n == 0) return vector<int>(m + 1, 0);
    vector<int> kmp(n + 1);
    vector<int> res(m + 1);
    kmp[0] = -1;
    kmp[1] = 0;
    for (int i = 2, curLen = 0; i <= n; i++) {
        while (curLen != -1 && s[i] != s[curLen + 1]) curLen = kmp[curLen];
        kmp[i] = ++curLen;
    }
    for (int i = 1, curLen = 0; i <= m; i++) {
        while (curLen != -1 && t[i] != s[curLen + 1]) curLen = kmp[curLen];
        res[i] = ++curLen;
    }
    return res;
}

array<int, 3> solve(const int p, const bool rev) {
    string s1 = "*", s2 = "*";
    for (int i = p; i <= N; i++) s2 += S[i];
    for (int i = 1; i < p; i++) s1 += S[i];
    vector<int> match2 = match(s2, T);
    reverse(s1.begin() + 1, s1.end());
    reverse(T.begin() + 1, T.end());
    vector<int> match1 = match(s1, T);
    reverse(T.begin() + 1, T.end());
    reverse(match1.begin() + 1, match1.end());
    int len = 0;
    int lS = 0;
    int lT = 0;
    for (int i = 0; i <= M; i++) {
        const int lenR = i == 0 ? 0 : match2[i];
        const int lenL = i == M ? 0 : match1[i + 1];
        if (lenL + lenR > len) {
            len = lenL + lenR;
            lS = rev ? N - (p + lenR - 1) + 1 : p - lenL;
            lT = i - lenR + 1;
        }
    }

    return {len, lS, lT};
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> S >> T;
    S = '*' + S;
    T = '*' + T;
    N = sz(S) - 1;
    M = sz(T) - 1;
    array<int, 3> ans = {0, 0, 0};
    for (int p = 1; p <= N; p++) ans = max(ans, solve(p, false));
    reverse(S.begin() + 1, S.end());
    for (int p = 1; p <= N; p++) ans = max(ans, solve(p, true));
    cout << ans[0] << '\n' << ans[1] - 1 << ' ' << ans[2] - 1;
    return 0;
}

• Subtask 1: 15 / 15