Задача на префикс-функцию
Попалась задача с неприятным ограничением.
Номер 123. Ограничение в том, что надо решить задачу использую только префикс-функцию без hash функции или чего-то другого. Буду благодарен за решение.
Я пытался приделывать перевернутую строку и по ней уже считать префикс-функцию. Но алгоритм оказался нерабочим
Ответы (1 шт):
Если не использовать алгоритм Манакера, а только префикс-функцию, то можно так:
Проходим диапазон длин 2..Len(s) поочередно, добавляем к подстроке s[1..n] спецсимвол, не встречающийся в строке, и перевернутую подстроку. Считаем префикс функцию - если её последний элемент больше единицы - нашли префикс-палиндром соответствующей длины.
Почему вставлять спецсимвол - чтобы 'aaa' давало 3, а не 6.
Почему по шагам - префикс-функция дает палиндром максимальной длины.
(Может, какой-то трюк можно придумать, начав с максимальной длины, и проходить не все длины)
P.S. Упомянутый в начале алгоритм позволяет за линейное время всё это сделать.