Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
A palindrome is a string of characters that reads equally in both directions (left to right and right to left).
Given an arbitrary string S, consider an lexicographically ordered list of all the different palindromes that can be obtained by deleting and rearranging characters in the original string.
It is required to exclude from the specified list those palindromes which are lexicographically less than given string T.
If after that list is still longer than n, the extra palindromes from the end should also be removed.
The first two lines of the input contain strings S and T, consisting of digits and lowercase letters of the Latin alphabet.
They are followed by an integer n.
The output must contain all the remaining palindromes in the list in lexicographic order.
If there are none, the output should be an empty string.
0 < |T| ≤ |S| ≤ 100,
0 < n ≤ 2 ⋅ 104
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|
Можно, конечно, перебирать все возможные комбинации заданного набора символов в лексикографическом порядке, поочередно проверяя каждую из них на палиндромность. Однако это потребует от нас гораздо больше времени, чем мы можем себе позволить.
С другой стороны, мы можем перебрать все возможные половинки палиндромов, дополняя их по ходу дела, тем самым избегая вариантов перебора строк, заведомо не являющихся палиндромами.
Однако порядок следования палиндромов может отличаться от порядка их половинок. Например, половинки 'cba' и 'cbaa', дают нам палиндромы: 'cbaabc' и 'cbaaaabc', соответственно.
Отчасти по этой же причине нам будет сложно определить, когда остановиться, а также понять, какие из палиндромов после сортировки полученного списка выйдут за пределы заданного n.
Предлагаемый подход основан на полном лексикографическом переборе всех возможных комбинаций из заданного набора символов, однако использует ряд эвристик для отсечения заведомо ложных путей решения. По сути он объединяет идеи вышеописанных подходов, частично дополняя их.
Будем писать решение в виде рекурсивной функции, которая на входе принимает аргумент i — указывающий текущую позицию в выходной строке. В нее она поочередно подставляет каждый из имеющихся у нас в наборе символов и запускается рекурсивно для i + 1.
Таким образом, при каждом ее вызове у нас уже будет собрана некоторая строка P длины i, в конец которой будут добавляться новые символы.
Естественно, при выборе символов нам следует учитывать наше положение относительно секущей строки T.
Так, если строка P является префиксом строки T, то и перебор нужно начинать с символа T[i].
Если же это не так, либо длина строки T меньше текущего i, тогда мы можем начинать перебор с наименьшего доступного нам символа.
Во избежание лишних сравнений со строкой T, дополним нашу рекурсивную функцию еще одним булевым аргументом,
который будет равен 1, если собранная ранее строка P совпадает с соответствующим префиксом строки T,
и будет равен 0 во всех остальных случаях.
Далее, выбрав очередной символ c и подставив его в конец строки P,
мы можем попытаться сформировать пару новых палиндромов: нечетный P + c + P′ и четный P + c + c + P′.
При этом также стоит проверить число доступных нам символов, сравнив его с числом уже использованных.
Пусть у нас N[c] — указывает исходное количество символов c,
M[c] — количество символов c, встречавшихся в строке P.
Таким образом для получения нечетного палиндрома нам достаточно проверить условие (2 * M[c] ≤ N[c] + 1),
а для четного — (2 * M[c] ≤ N[c]).
Однако при этом не учитываются все остальные символы, встречавшиеся ранее в строке P.
Но здесь мы можем воспользоваться следующим фактом.
Если некоторый префикс P не сможет быть продлен до четного палиндрома,
то процесс формирования новых палиндромов на нем будет завершен.
Т.е. ни один последующий префикс, имеющий P в качестве подпрефикса,
не сможет быть продлен до палиндрома.
Для доказательства этого факта нам достаточно пойти от противного.
Если бы в действительности существовал какой либо палиндром,
половинка которого имеет вид P + Q,
то среди его суффиксов обязательно нашелся бы и P′.
А тогда мы могли бы получить P + P′,
что противоречит исходной предпосылке.
Таким образом, чтобы пропустить этап создания новых палиндромов в последующих запусках рекурсивной функции, будем передавать в нее еще один булев аргумент, который сообщает о том, является ли префикс P половинкой четного палиндрома или нет.
Созданные таким образом палиндромы не выводятся сразу, а откладываются в специальную структуру данных, где ждут своего часа.
В качестве такой структуры будем использовать двумерный массив D[i][c] — содержащий списки палиндромов, префиксы которых совпадают с полученной ранее строкой P, а в i-й позиции находится символ c. При этом сами палиндромы записываются в виде индексов своих позиций, противоположных i.
Перед самым первым запуском рекурсивной функции, выполняется инициализация D[0][c].push(0), для всех допустимых c ≥ T[0].
При создании нечетного палиндрома P + c + P′, создается новая запись в массиве D[i + 1][P[i − 1]].push(i − 1),
а при создании четного P + c + c + P′: D[i + 1][c].push(i).
Теперь можно сказать, что при подстановке очередного символа c в конец строки P,
нам следует выполнить обход всех l, содержащихся в списке D[i][c].
Для каждого такого l > 0, продлеваем соответствующий палиндром,
путем создания новой записи D[i + 1][P[l − 1]].push(l − 1).
Если же найдется l = = 0, это будет означать, что в этой позиции заканчивается созданный ранее палиндром,
тогда выводим полученную строку {P + c} в выходной поток.
Если же в какой-то момент у нас окажется, что не нашлось ни одного палиндрома с префиксом P
либо число всех отданных палиндромов превысило n, процедура завершается.
Стоит отметить, что во избежание мусорных данных, при откате рекурсии назад,
содержимое подмассива D[i] следует чистить.
Таким образом, мы переберем все возможные префиксы наших палиндромов.
Все прочие строки, не являющиеся таковыми,
просматриваться не будут.
В силу этого можно утверждать, что время работы алгоритма линейно
зависит от размера ответа.