Палиндром из букв
Найдите в тексте самый длинный палиндром из букв: кусок, который читается одинаково слева направо и справа налево, если не смотреть на пробелы, знаки препинания, цифры и переводы строк. Регистр не важен, ё и е — одна буква. Буквы — всё, что считается буквой в Юникоде: кириллица, латиница и другие.
Выведите его так, как он стоит в тексте: от первой буквы палиндрома до последней, со всеми знаками между ними. Если самых длинных несколько, выведите тот, что начинается раньше.
В третьем тесте 300 000 знаков «Войны и мира», в четвёртом — «Евгений Онегин».
Вход
Текст в кодировке UTF-8, одна или несколько строк, всего от 1 до 3 · 10⁵ знаков; в нём есть хотя бы одна буква. Длины считаются в знаках, а не в байтах.
Выход
В первой строке — число букв в палиндроме. Во второй — сам кусок текста, где каждый перевод строки заменён пробелом.
Примеры
Пример 1
А роза упала на лапу Азора!
21 А роза упала на лапу Азора
Пример 2
Я иду с мечем, судия. — Гавриил Державин
15 Я иду с мечем, судия
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала выпишите буквы подряд, приведя их к одному виду, и запомните для каждой, где она стоит в тексте. Тогда задача — самый длинный палиндром в строке, а кусок текста восстанавливается по местам первой и последней буквы.
2Подсказка 2
У палиндрома есть центр — буква или промежуток. Расширяться от каждого центра заново дорого, если букв одного вида много. Нельзя ли взять радиус готовым из зеркального центра?
3Идея
Алгоритм Манакера. Между буквами ставим разделитель, которого в строке нет: тогда у палиндромов обеих чётностей есть центр-позиция, и радиус в новой строке равен длине палиндрома в буквах. Внутри самого правого найденного палиндрома радиус центра не меньше радиуса отражённого центра, урезанного до границы.
4Разбор
Для позиции i с радиусом k палиндром начинается с буквы (i − k) / 2 и содержит k букв. Берём наибольший k, а при равенстве — меньшее начало. Потом по таблице мест берём кусок текста от первой буквы до последней и заменяем переводы строк пробелами. В Go текст надо разобрать на руны: буквы кириллицы занимают по два байта.
4+Решение
5Сложность
O(n): выписать буквы — один проход, Манакер — меньше 2m сравнений для строки с разделителями длины m.
6Типичные ошибки
- Расширяться от каждого центра. Это
wrong.py. На романе и поэме палиндромы короткие — в «Онегине» самый длинный семь букв, — и он успевает. Но в пятом тесте почти все буквы «а», между ними пробелы и тире, и каждый центр расширяется на тысячи шагов. - Только нечётные. В шестом тесте самый длинный палиндром чётной длины, 8000 букв.
- Ё и регистр. В седьмом тесте самый длинный — «Ёлка, вот ов, а клЕ»: без правила «ё = е» и без перевода в строчные он не находится.
- Кусок без знаков. Выводить надо текст как он есть, со знаками, пробелами и разными регистрами, а не выписанные буквы.