oj.uz

답안 #646597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646597 2022-09-30T09:28:45 Z Elias_Obeid Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 327 ms 600 KB 
#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

# 결과 실행 시간 메모리 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