Submission #646597

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646597	2022-09-30T09:28:45 Z	Elias_Obeid	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	327 ms	600 KB

necklace

#include <bits/stdc++.h>

std::vector<int> kmpString(const std::string &initial_string)
{
    int string_size = (int)initial_string.size();
    std::vector<int> prefix_function(string_size);
    for (int i = 1; i < string_size; ++i)
    {
        int j = prefix_function[i - 1];
        while (j > 0 && initial_string[i] != initial_string[j])
        {
            j = prefix_function[j - 1];
        }

        if (initial_string[i] == initial_string[j])
        {
            ++j;
        }
        prefix_function[i] = j;
    }
    return prefix_function;
}

void getBest(const std::string &S, const std::string &T,
             int &maximum_length, int &indexS, int &indexT, bool reveresedT)
{
    int N = (int)S.size();
    int M = (int)T.size();

    for (int i = 0; i < N; ++i)
    {
        std::string X = S.substr(i) + '#' + T;
        std::string Y = T + '#' + S.substr(0, i);
        std::reverse(Y.begin(), Y.end());

        std::vector<int> prefix_functionX = kmpString(X);
        std::vector<int> prefix_functionY = kmpString(Y);

        int indexX = i, indexY = N - i;
        for (int j = 0; j <= M; ++j)
        {
            int current_length = prefix_functionX[indexY + j] + prefix_functionY[indexX + M - j];
            if (current_length > maximum_length)
            {
                int current_indexS = i - prefix_functionY[indexX + M - j];
                int current_indexT = j - prefix_functionX[indexY + j];
                if (reveresedT)
                {
                    current_indexT = M - 1 - (j + prefix_functionY[indexX + M - j] - 1);
                }
                maximum_length = current_length;
                indexS = current_indexS;
                indexT = current_indexT;
            }
        }
    }
}

int main()
{
    std::string S, T;
    std::cin >> S >> T;

    int maximum_length = 0, indexS = -1, indexT = -1;
    for (int type = 0; type < 2; ++type)
    {
        getBest(S, T, maximum_length, indexS, indexT, static_cast<bool>(type));
        std::reverse(T.begin(), T.end());
    }
    std::cout << maximum_length << std::endl;
    std::cout << indexS << " " << indexT;
    return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	290 ms	600 KB	Output is correct
2	Correct	239 ms	376 KB	Output is correct
3	Correct	327 ms	340 KB	Output is correct
4	Correct	235 ms	380 KB	Output is correct
5	Correct	180 ms	340 KB	Output is correct
6	Correct	197 ms	384 KB	Output is correct
7	Correct	240 ms	388 KB	Output is correct
8	Correct	247 ms	384 KB	Output is correct
9	Correct	261 ms	384 KB	Output is correct