| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
A palindrome refers to a sequence of characters that reads the same in both directions (from left to right and from right to left).
A palindrome is compound if words of arbitrary length are used like characters.
It means that words located symmetrically from its center are the same.
Moreover, the words themselves do not have to be palindromes.
Consider a string, S, composed of digits and lowercase Latin alphabet letters.
The task is to split the original string into the maximum number of words,
ensuring that the resulting set is a compound palindrome.
The input consists of a single line, S.
The output should contain a sequence of word lengths, where the right ends of the words are located in the left half of the string.
If such a sequence does not exist, the output should remain empty.
1 ≤ |S| ≤ 2 ⋅ 106.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|
Для начала разделим исходную строку на две части: L = S[0: m − 1], R = S[n − m: n − 1], где n — длина строки, m = n / 2.
Тогда всем словам, содержащимся в левой половине, будут соответствовать слова, содержащиеся в правой и наоборот.
Исключение составляет центральное (возможно пустое) слово, выступающее в роли ядра палиндрома.
Будем на каждом шаге искать минимально возможный непустой префикс строки L, совпадающий с суффиксом строки R.
Докажем, что выбор минимального такого префикса здесь будет являться оптимальным.
Предположим, что вместо минимального префикса [a] мы выбрали префикс большей длины.
Тогда префикс и суффикс указанного префикса должны совпадать с [a].
При этом, он обязан быть как минимум в 2 раза больше [a],
т.к. иначе [a] уже не будет минимальным, что противоречит исходной предпосылке.
Тогда указанный префикс можно записать как [a][b][a],
а исходная строка примет вид: [a][b][a][…][a][b][a].
Как можно видеть, выбор [a] даст нам больше слов в ответе.
При этом, внутренняя часть строки […] в обоих случаях останется незатронутой.
Для эффективного решения поставленной задачи заведем два вспомогательных массива P и T. Инициализируем их нулями.
Массив P будем последовательно заполнять значениями префикс-функции для ранее просмотренных префиксов строки L.
Иначе говоря, P[k] будет хранить длину наибольшего префикса подстроки L[0: k − 1], совпадающего с ее суффиксом.
Напомним, что эффективный алгоритм позволяет заполнить такой массив за линейное время.
В массиве T будем сохранять результаты от сравнений всех предыдущих суффиксов строки R с префиксами строки L.
Двигаясь справа налево в строке R найдем ближайшее j, при котором R[j] = L[0].
Посимвольным сравнением будем искать максимальное k: R[j: j + k] = L[0: k].
Если j + k = n − 1, значит искомый префикс был найден. Иначе запоминаем T[j]← k + 1 и переходим к следующему j.
Если при посимвольном сравнении мы достигли k, при котором t = T[j + k] > 0, это означает,
что в позиции j + k, уже встречалось совпадение: R[j + k: j + k + t − 1] = L[0: t − 1].
Тогда логично предположить, что сложив два префикса L[0: k] + L[0: t − 1]
мы ожидали бы получить префикс L[0: k + t − 1].
Чтобы избежать лишних сравнений проверяем значение q = P[k + t − 1].
Если q = t, тогда мы можем продолжить поиск уже с позиции j + k + t.
Иначе запоминаем T[j]← k + 1 и переходим к следующему j.
Отметим, что здесь q не может быть больше t, т.к. это означало бы,
что имело место еще одно совпадение между позициями j и j + k.
Однако это невозможно в силу выбора j и k.
Таким образом, мы последовательно обойдем все подозрительные суффиксы строки R
в порядке возрастания их длин z = n − j.
Обратим внимание, что массив P здесь заполняется лишь в диапазоне от 0 до z.
Если при сравнении строк удалось нарастить совпадающий префикс на T[j + k],
тогда длина полученной строки войдет в T[j], а следовательно
повторное обращение к T[j + k] уже не потребуется.
Если же совпадение не было найдено, то происходит откат j
как минимум на одну позицию назад.
Иначе говоря, в среднем на одну итерацию по j мы обращаемся не более,
чем к двум элементам из T.
В таком случае можно утверждать, что время поиска линейно зависит
от длины искомого префикса.
Общее время алгоритма при этом составит O(n).