Ограничение времени на тест: 5 секунд
Ограничение памяти на тест: 512 мегабайтВам дана строка
s
длиныn
(n
≤ 5000). Вы можете выбрать любой правильный префикс этой строки, который также является ее суффиксом, и удалить либо выбранный префикс, либо соответствующий суффикс. Затем вы можете применить аналогичную операцию к результирующей строке и так далее. Какова минимальная длина конечной строки, которая может быть достигнута после применения оптимальной последовательности таких операций?Входные данные
Первая строка каждого теста содержит строкуs
, состоящую из маленьких английских букв.Выходные данные
Выведите единственное целое число - минимальную длину конечной строки, которая может быть достигнута после применения оптимальной последовательности таких операций.Примеры
+-------+--------+----------------------------------+ | Input | Output | Explanation | +-------+--------+----------------------------------+ | caaca | 2 | caaca → ca|aca → aca → ac|a → ac | +-------+--------+----------------------------------+ | aabaa | 2 | aaba|a → a|aba → ab|a → ab | +-------+--------+----------------------------------+ | abc | 3 | No operations are possible | +-------+--------+----------------------------------+
Вот что мне удалось сделать до сих пор:
Вычислить префиксную функцию для всех подстрок данной строки в O (n ^ 2)
Проверьте результат выполнения всех возможных комбинаций операций в O (n ^ 3)
Мое решение проходит все тесты при n
≤ 2000, но превышает ограничение по времени, когда 2000 < n
≤ 5000. Вот его код:
#include <iostream>
#include <string>
using namespace std;
const int MAX_N = 5000;
int result; // 1 less than actual
// [x][y] corresponds to substring that starts at position `x` and ends at position `x + y` =>
// => corresponding substring length is `y + 1`
int lps[MAX_N][MAX_N]; // prefix function for the substring s[x..x+y]
bool checked[MAX_N][MAX_N]; // whether substring s[x..x+y] is processed by check function
// length is 1 less than actual
void check(int start, int length) {
checked[start][length] = true;
if (length < result) {
if (length == 0) {
cout << 1; // actual length = length + 1 = 0 + 1 = 1
exit(0); // 1 is the minimum possible result
}
result = length;
}
// iteration over all proper prefixes that are also suffixes
// i - current prefix length
for (int i = lps[start][length]; i != 0; i = lps[start][i - 1]) {
int newLength = length - i;
int newStart = start + i;
if (!checked[start][newLength])
check(start, newLength);
if (!checked[newStart][newLength])
check(newStart, newLength);
}
}
int main()
{
string str;
cin >> str;
int n = str.length();
// lps calculation runs in O(n^2)
for (int l = 0; l < n; l++) {
int subLength = n - l;
lps[l][0] = 0;
checked[l][0] = false;
for (int i = 1; i < subLength; ++i) {
int j = lps[l][i - 1];
while (j > 0 && str[i + l] != str[j + l])
j = lps[l][j - 1];
if (str[i + l] == str[j + l]) j++;
lps[l][i] = j;
checked[l][i] = false;
}
}
result = n - 1;
// checking all possible operations combinations in O(n^3)
check(0, n - 1);
cout << result + 1;
}
В: Есть ли более эффективное решение?
источник
Ответы:
Вот один из способов получить логарифмический фактор. Позвольте
dp[i][j]
быть правдой, если мы можем достичь подстрокиs[i..j]
. Затем:Теперь итерации извне:
Мы можем предвычисления самый длинный матч для каждой стартовой пары
(i, j)
вO(n^2)
с рецидивом,Это позволит нам проверить соответствие подстроки, которая начинается в индексах
i
иj
вO(1)
. (Нам нужны как правое, так и левое направление.)Как получить логарифмический фактор
Мы можем придумать способ придумать структуру данных, которая позволила бы нам определить,
в
O(log n)
, учитывая, что мы уже видели эти значения.Вот код C ++ с деревьями сегментов (для правого и левого запросов
O(n^2 * log n)
), который включает генератор тестов Бананона. Для 5000 символов «а» он работал в 3,54 с, 420 МБ ( https://ideone.com/EIrhnR ). Чтобы уменьшить память, одно из деревьев сегментов реализовано в одной строке (мне все еще нужно исследовать то же самое с левыми запросами, чтобы еще больше уменьшить память).А вот код JavaScript (без улучшения коэффициента логарифмирования), чтобы показать, что повторение работает. (Чтобы получить логарифмический коэффициент, мы заменяем внутренние
k
циклы одним запросом диапазона.)источник
i
от 64-й строки начало 99-й довольно сложно обдумать - это намеренно? Объявления циклов в 98 и 99, кажется, оставляютi
вMAX_N
для остальной части области цикла строки 98? (C ++ версия)i
было только для объема этого цикла из четырех строк, но это могло бы показаться странным. Спасибо за указание - я изменил это, хотя изменение не влияет на выполнение кода.