Submission #1298744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298744		martin_nedev	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	156 ms	572 KiB

necklace

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

struct Result
{
    int length, start_a, start_b;
    Result(){}
    Result(int length, int start_a, int start_b)
        :length(length), start_a(start_a), start_b(start_b){}
};

void getPrefixFunction(const string& S, vector <int>& pi)
{
    int N = S.size();
    pi[0] = 0;
    for (int i = 1, j = 0; i < N; i++)
    {
        while (j > 0 && S[i] != S[j])
            j = pi[j-1];

        if (S[i] == S[j])
            j++;

        pi[i] = j;
    }
}

void KMP(const string& text, const string& pattern, vector<int>& pi, vector<int>& longestMatch)
{
    int N = text.size();
    int M = pattern.size();

    if (M == 0 || N == 0)
        return;

    getPrefixFunction(pattern, pi);

    for (int i = 0, j = 0; i < N; i++)
    {
        while (j > 0 && text[i] != pattern[j])
            j = pi[j-1];

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

        longestMatch[i] = j;

        if (j == M)
            j = pi[j-1];


    }
}
Result Solve(const string& A, const string& B)
{
    Result res(0, 0, 0);

    int N = A.size();
    int M = B.size();

    vector <int> pi_1(N, 0);
    vector <int> pi_2(N, 0);

    vector <int> longestMatch_1(M, 0);
    vector <int> longestMatch_2(M, 0);

    string A1, A2;
    string B_rev = B;

    reverse(B_rev.begin(), B_rev.end());

    for (int i = 0; i <= N; i++)
    {
        A1 = A.substr(0, i);
        reverse(A1.begin(), A1.end());
        A2 = A.substr(i);


        KMP(B_rev, A1, pi_1, longestMatch_1);
        KMP(B, A2, pi_2, longestMatch_2);


        for (int j = 0; j <= M; j++)
        {
            // A = [...U][V...]
            // B = [...V][U...]

            int len_U = (j < M) ? longestMatch_1[M-1-j]: 0;
            int len_V = (j > 0) ? longestMatch_2[j-1]: 0;

            int total_length = len_U+len_V;

            if (total_length > res.length)
            {
                res.length = total_length;
                res.start_a = i-len_U;
                res.start_b = j-len_V;

                /*cout << endl;
                cout << A.substr(0, i) << " " << A.substr(i) << endl;
                cout << B.substr(0, j) << " " << B.substr(j) << endl;
                cout << len_U << " " << len_V << endl;*/
            }
        }
    }

    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    string A, B;
    cin >> A >> B;

    Result res1 = Solve(A, B);
    reverse(B.begin(), B.end());
    Result res2 = Solve(A, B);
    res2.start_b = B.size()-res2.length-res2.start_b;

    if (res1.length > res2.length)
    {
        cout << res1.length << endl;
        cout << res1.start_a << " " << res1.start_b << endl;
    }

    else
    {
        cout << res2.length << endl;
        cout << res2.start_a << " " << res2.start_b << endl;
    }


    return 0;
}

• Subtask 1: 15 / 15