Submission #1323774

#TimeUsernameProblemLanguageResultExecution timeMemory
1323774arvind215271Necklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
101 ms35596 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> getLPSRangeFull(const string &s, int L, int R) {
    int n = s.size();
    vector<int> lps(n, 0);

    int l = 0;
    for (int i = L + 1; i <= R; i++) {
        while (l > 0 && s[i] != s[L + l]) {
            l = lps[L + l - 1] - L;
        }
        if (s[i] == s[L + l]) l++;
        lps[i] = L + l;
    }
    return lps;
}

vector<int> getKMPRangeFull(const string &text,
                            const string &pattern,
                            int pL, int pR,
                            vector<vector<int>> &dp) {

    vector<int> lpsAbs = getLPSRangeFull(pattern, pL, pR);
    int n = text.size();
    int m = pR - pL + 1;

    vector<int> lps2(n, 0);

    int j = 0;
    int maxi = 0;
    int maxIndex1 = -1;
    int maxIndex2 = -1;

    for (int i = 0; i < n; i++) {
        while (j > 0 && pattern[pL + j] != text[i]) {
            j = (lpsAbs[pL + j - 1] - pL);
        }

        if (pattern[pL + j] == text[i]) j++;
        lps2[i] = j;

        if (lps2[i] > maxi) {
            maxi = lps2[i];
            maxIndex1 = i;
            maxIndex2 = lps2[i];
        }

        if (j == m) {
            j = (lpsAbs[pR] - pL);
        }

        // ===============================
        // YOUR DP LOGIC (UNCHANGED)
        // ===============================
        int currentLevel = m;
        int previousLevel = currentLevel - lps2[i] - 1;
        int startIndex = i - lps2[i] + 1;
        int beforeStartIndex = startIndex - 1;

        if (startIndex > 0 && previousLevel >= 0 && dp.size() > previousLevel) {
            int beforeLength = dp[previousLevel][beforeStartIndex];
            int currentAns = beforeLength + lps2[i];

            // the start of the text is from... beforeStartInex - beforeLength ig??
            
            int start1 = startIndex - beforeLength;
            int start2 = pL;

            

            if (currentAns > maxi) {
                maxi = currentAns;
                maxIndex1 = start1;
                maxIndex2 = start2;
                
            }
        }
        // ===============================
    }

    dp.push_back(lps2);
    return {maxi, maxIndex1, maxIndex2, n, m, pL};
}

vector<int> solve(const string &A, const string &B) {
    int N = A.size();
    vector<vector<int>> dp;

    int best = 0;
    vector<int> ans;

    for (int i = N - 1; i >= 0; i--) {
        auto cur = getKMPRangeFull(B, A, i, N - 1, dp);
        if (cur[0] > best) {
            best = cur[0];
            ans = cur;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string jill, jane;
    cin >> jill >> jane;

    int N = jill.size();
    int M = jane.size();

    auto ans1 = solve(jane, jill);

    string revJane = jane;
    reverse(revJane.begin(), revJane.end());
    auto ans2 = solve(revJane, jill);

    // start1 -> revJill
    // start2 -> jane always

    // print ans1 and ans2.
    // for (int i = 0; i < ans1.size(); i++) {
    //     cout << ans1[i] << " ";
    // }
    // cout << endl;

    // for (int i = 0; i < ans2.size(); i++) {
    //     cout << ans2[i] << " ";
    // }
    // cout << endl;


    bool useRev;
    if (ans1[0] >= ans2[0]) {
        useRev = false;
    }
    else {
        useRev = true;
    }


    auto ans = useRev ? ans2 : ans1;

    int len = ans[0];

    int start1 = ans[1];
    int end1 = ans[1] + len - 1;

    int start2 = ans[2];
    int end2 = ans[2] + len - 1;

    // int pL = ans[5];

    // int startB = endB - len + 1;
    // int startA = pL;

    if (useRev == true) {
        // int realStartB = M - 1 - endB;
        // realStartB -= (len - 1);
        // startB = realStartB;
        int temp = start2;
        start2 = M - 1 - end2;
        end2 = M - 1 - temp;

    

    }

    // cjehck if start is end is eual to len.
    


    cout << len << "\n";

    cout << start1 << " " << start2 << endl;

    return 0;
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...