Submission #1328695

#TimeUsernameProblemLanguageResultExecution timeMemory
1328695trungcanNecklace (Subtask 4) (BOI19_necklace4)C++17
15 / 15
214 ms572 KiB
#include <bits/stdc++.h>
#define piii pair<int, pair<int, int>>
#define fi first
#define se second

using namespace std;

const int N = 6005;

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

void KMP(string &S, int *p){
    for (int i = 1; i < (int)S.size(); ++i){
        int k = p[i - 1];
        while (k && S[i] != S[k]) k = p[k - 1];

        p[i] = k + (S[i] == S[k]);
    }
}

piii calc(bool rev){
    string t1 = T, t2 = T;
    reverse(t2.begin(), t2.end());
    piii ans = {-1, {0, 0}};
    for (int i = 0; i < n; ++i){
        string s1 = S.substr(0, i), s2 = S.substr(i, n - i);
        reverse(s1.begin(), s1.end());
        s2 = s2 + "#" + t1; s1 = s1 + "#" + t2;
        KMP(s2, p1); KMP(s1, p2);

//        if (i == 5 && rev){
//            cout << s2 << "\n";
//            for (int j = 0; j < (int)s2.size(); ++j) cout << p1[j] << " "; cout << "\n";
//            cout << s1 << "\n";
//            for (int j = 0; j < (int)s1.size(); ++j) cout << p2[j] << " "; cout << "\n";
//        }

        for (int j = 0; j < m; ++j){
//            if (p1[n - i + j] + p2[i + m - j] == 4) cout << rev << "\t" << i - p2[i + m - j] << " " << j << "\t" << (rev ? m - (j + p2[i + m - j] - 1) - 1 : j - p1[n - i + j]) << "\n";
            ans = max(ans, {p1[n - i + j] + p2[i + m - j],
                      {i - p2[i + m - j], rev ? m - (j + p2[i + m - j] - 1) - 1 : j - p1[n - i + j]}});
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> S >> T;
    n = (int)S.size(); m = (int)T.size();

    piii res = calc(0);
    reverse(T.begin(), T.end());
    res = max(res, calc(1));

    cout << res.fi << '\n' << res.se.fi << " " << res.se.se;
}
#Verdict Execution timeMemoryGrader output
Fetching results...