# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
646597 | Elias_Obeid | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 327 ms | 600 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |