Очень скоро наступит календарная зима и все осенние дела нужно закончить.
Подходит к концу и наш осенний конкурс. Вряд ли кто-то из участников успеет преодолеть 9 уровень.
Поэтому, с наступлением зимы, будем все замораживать.
Начиная с 1 декабря, будут "замораживаться" результаты уровней.
1 декабря --- 1 уровень,
2 декабря --- 2 уровень,
и т.д.,
9 декабря --- 9 уровень.
"Замораживаться" --- значит, что участники оказавшиеся на
этом уровне в этот день больше на другие уровни не переходят и их
программы не тестируются. Для них конкурс закончен.
Торопитесь! Осталось всего несколько дней.
Теперь немного слов участникам, которые подключились недавно. Эти участники повторяют
те же ошибки, что и старые участники. Чтобы избежать многих ошибок, нужно прочитать все рассылки
этого конкурса.
Сегодня разберёмся с задачей чётвёртого уровня. Это первая, по-настоящему
интересная задача конкурса.
Палиндром одной вставкой
Эта задача имеет простое, быстрое и красивое решение. Нужно разбить заданную строку на части и одну из
них перевернуть. Перевернуть --- значит записать все символы в обратном порядке.
Введём обозначение. Если X --- строка, то [X] --- перевёрнутая строка.
Значит строки X[X] и [X]X --- палиндромы.
S --- заданная строка. Тогда S=AB[A], где A и B --- какие-то строки, возможно пустые.
Например, если S --- палиндром, то B --- пустая строка.
Находим самую длинную А. После этого задача сводится к решению для B.
Строка B устроена так. B=C[C]D и B=EF[F]. Определим, что короче D или E, вставлять
нужно одну из них перевернутую.
Если короче D, то искомая строка A[D]С[С]D[A].
Если короче E, то искомая строка AEF[F][E][A].