Палиндромы

Палиндром. Какие бывают палиндромы?

Палиндромы — это слова, которые читаются одинаково в обоих направлениях: слева направо и справа налево. Самым длинным в мире палиндромом, состоящим из одного слова, принято считать финское слово SAIPPUAKIVIKAUPPIAS (торговец щелоком — мыльным камнем). В английском языке самый длинный палиндром — REDIVIDER (своего рода перегородка).

В русском языке довольно много слов-палиндромов. Приводим их группами по количеству букв.

Палиндромы из 2 букв

• АА — так малыши говорят, когда садятся на горшок
• ИИ — искусственный интеллект
• ЯЯ — посёлок городского типа в Кемеровской области

Палиндромы из 3 букв

• АБА — еврейское мужское имя, а также город в Нигерии
• АГА — ядовитая тропическая жаба
• АДА — женское имя
• АЗА — женское имя
• АКА — одна из групп пигмеев в Африке
• АЛА — конное вспомогательное подразделение римской армии
• АМА — японская ныряльщица за жемчугом
• АРА — род птиц семейства попугаевых
• АТА — в древнегреческой мифологии богиня обмана и глупости
• АША — город в Челябинской области
• БОБ — спортивные сани и плод растения семейства бобовых
• ДЕД — пожилой мужчина
• ИХИ — бог музыки у древних египтян
• КОК — корабельный повар
• МИМ — актер, работающий в жанре пантомимы
• ОКО — глаз
• ПОП — просторечное наименование священника
• ПУП — пупок
• СОС — сигнал о помощи в море
• ТИТ — мужское имя
• ТУТ — тутовое дерево
• УШУ — китайское воинское искусство
• ШИШ — то же, что кукиш

Палиндромы из 4 букв

• АББА — знаменитый шведский квартет
• АВВА — собака Айболита
• АККА — главная гусыня из сказки про Нильса
• АЛЛА — женское имя
• АННА — женское имя
• АССА — название фильма
• ОТТО — мужское имя

Палиндромы из 5 букв

• АДАДА — фильм Квон-Тэк Има (Ю. Корея).
• АЗИЗА — женское имя
• ВЕНЕВ — город в Тульской области
• ДЕБЕД — река в Армении и Грузии
• ДОВОД — аргумент в споре
• ДОРОД — хороший урожай (устар.), антоним к НЕДОРОД (неурожай)
• ДОХОД — прибыль
• ЗАКАЗ — то, что заказали
• КАБАК — старинный аналог бара
• КАЗАК — житель Дона или Кубани
• КИЛИК — древнегреческий сосуд плоской формы на короткой ножке
• КИНИК — циник (устар.).
• КОВОК — один удар молотом (устар.) — отсюда глагол ковать
• КОЛОК — стержень для натяжения струн на гитаре
• КОМОК — что-то скомканное
• КОПОК — действие, производимое лопатой при копании
• КОТОК — ласковое название кота (устар.)
• МАДАМ — обращение к замужней женщине
• НАГАН — пистолет
• НАТАН — еврейское имя
• НИЖИН — город, родина Марка Бернеса.
• НОЙОН — монгольский аристократ
• ПОТОП — наводнение
• РАДАР — радиолокатор
• РЕПЕР — геодезический знак
• РОТОР — подвижная часть механизма
• СОРОС — американский бизнесмен
• ТАНАТ — (Фанат, Танатос) брат-близнец бога сна Гипноса
• ТОПОТ — шум шагов
• ШАБАШ — гулянка нечисти
• ШАЛАШ — палатка из веток

Палиндромы из 6 букв

• МИЛЛИМ — 1/000 тунисского динара.
• НЯННЯН — китайская богиня, защищающая младенцев и помогающая при родах
• ТИЛЛИТ — минерал, сульфид олова и свинца
• ТИННИТ — богиня в Карфагене
• ТОММОТ — город в Якутии

Палиндромы из 7 букв

• АНИСИНА — плод аниса
• АПОКОПА — отпадение звука в конце слова
• КИНОНИК — православное церковное песнопение
• РОТАТОР — аппарат для печати копий с рукописей, документов, чертежей
• ТАРТРАТ — соль винной кислоты

Примеры использования[править]

• «А роза упала на лапу Азора»:
  • А. Н. Толстой, «Золотой ключик» — с детства известно, что Мальвина, пытаясь научить Буратино правописанию, хорошим манерам или вообще чему-либо, диктует ему эту фразу.
  • А. Семёнов, книга-комикс

    В первоисточнике не без сарказма сообщается, что те, кто пострадал от этой верёвки, через какое-то время пошли на поправку: смогли правильно произносить слова вроде «боб», «поп», «Алла», «Анна», а один даже выдал без единой ошибки целую фразу «Тит еле летит».

    «Ябеда-Корябеда и её проделки» (новеллизация приключений Мурзилки) — лазутчики тестируют невидимую верёвку-перевёртыш, которая заставляет людей произносить слова наоборот. На их беду, один из «подопытных» произносит именно фразу «А роза упала на лапу Азора» (кусты роз и собака Азор в антураже прилагаются) и до, и после того, как споткнулся, из-за чего лазутчики пугаются, что верёвка не работает.

• М. А. Шолохов, «Тихий Дон» — монархист Капарин рассуждает, чем сменится власть большевиков: «молот, серп» наоборот — «престолом».
• Леонид Каганов в цикле своих пародий опубликовал сборник «Белых палиндромов». Как «белый стих» — это поэзия без рифмы, так «белый палиндром» подобен обычному и своей осмысленностью, и художественной ценностью, разве что наоборот не читается. Например: «УХО СМЕХА — МЕХИКО», «В ДЕБАГГЕРЕ БАГ HА ДИВО», «ША! ДОГ ЛИЛ ГОДОВ КАШУ» и «ЕШЬ ДРОЖЖИ ЖОПОЙ».
• Святослав Логинов:
  • «Кабак» — целый маленький рассказ, состоящий целиком из палиндромов.
  • Повесть «Тени большого города» — палиндромами разговаривают тени, что в силу не очень большого запаса реплик приводит к курьезам:

• Уругвайский полнометражный мультфильм «Анина», в котором несчастная девочка страдает от увлечения ее отца палиндромами. Собственно, и дочь он назвал тремя палиндромами: Анина Йатай Салас. Теперь за такое имя в школе ее дразнят «Капикуа» (по-каталански — «голова-хвост»).
• Манга «Karei Naru Shokutaku»: одного из персонажей зовут Эна (恵菜) Мэгуми (恵), всё вместе — 恵菜恵. При встрече она хвастается, что ее имя одинаково читается с любой стороны.
• Might and Magic V — фигурирует небольшой монашеский орден Drawkcab Monks («drawkcab» — это написанное задом наперёд слово «backward», т. е. «задом наперёд»). Они изучают палиндромы, и говорят почти исключительно таковыми.

Нажмите для проигрывания

Зеркальный дуэт Моцарта

• В эпоху барокко композиторы частенько увлекались сочинением произведений, которые можно одинаково успешно играть как с начала, так и с конца. К таковым относятся, например, «Крабий канон» Баха и (по слухам) «Вальс цветов» П. И. Чайковского. А в произведении «Путь мира» И. Мошелеса при повороте его на 180 градусов не меняется ни музыка, ни внешний вид записи (таким образом, оно является истинным музыкальным палиндромом).
• Песня «Странного Эла» Янковича «Bob» (стилистическая пародия на Боба Дилана) из них и состоит (включая название).
• Игорь Корнелюк, «Гимн Воланда» (саундтрек из «Мастер и Маргарита» Бортко) — палиндром SATOR AREPO TENET OPERA ROTAS слышится на заднем плане, создавая эффект, будто он часть музыки.
• Вокруг палиндрома SATOR AREPO TENET OPERA ROTAS построен фильм «Довод» Кристофера Нолана.

Это интересно

Русскоязычному миру эта игра слов может быть знакома благодаря экранизации романа М. А. Булгакова «Мастер и Маргарита». Предложение было положено на музыку как «Гимн Воланда» и использовалось в одном из главных саундтреков телесериала.

Активное развитие симметрического текста в России датируется второй половиной ХХ века. Его использовали в своей творческой деятельности и исследовали с лингвистической точки зрения такие писатели, как:

• Николай Ладыгин;
• Владимир Гершуни;
• Елена Кацюба;
• Герман Лукомников.

Сегодня палиндромы — забавное развлечение на досуге, не более. Но в давние имена им приписывали разнообразные магические свойства. Люди верили, что написание симметричного текста на стене дома или входной двери способно уберечь его хозяина от зла.

Дерево палиндромов

Дерево палиндромов (англ. palindromic tree, EERTREE) — структура данных, использующая другой, более мощный формат хранения информации обо всех подпалиндромах, чем размеры \(n\) палиндромов. Она была предложена Михаилом Рубинчиком на летних петрозаводских сборах в 2014-м году.

Лемма. В строке есть не более \(n\) различных подпалиндромов.

Доказательство. Пусть мы дописываем к строке по одному символу и в данный момент, записав \(r\) символов, имеем наибольший суффикс-палиндром \(s_{l:r}\). Пусть у него, в свою очередь, есть суффикс-палиндром \(s_{l’:r} = t\). Тогда он также имеет более раннее вхождение в строку как \(s_{l:l+r-l’} = t\). Таким образом, с каждым новым символом у строки появляется не более одного нового палиндрома, и если таковой есть, то это всегда наибольший суффикс-палиндром.

Этот факт позволяет сопоставить всем палиндромам строки сопоставить следующую структуру: возьмём от каждого палиндрома его правую половину (например, \(caba\) для \(abacaba\) или \(ba\) для \(abba\); будем рассматривать пока что только чётные палиндромы) и добавим все эти половины в префиксное дерево — получившуюся структуру и будем называть деревом палиндромов.

Наивный алгоритм построения будет в худшем случае работать за \(O(n^2)\), но это можно делать и более эффективно.

Построение за линейное время

Будем поддерживать наибольший суффикс-палиндром. Когда мы будем дописывать очередной символ \(c\), нужно найти наибольший суффикс этого палиндрома, который может быть дополнен символом \(c\) — это и будет новый наидлиннейший суффикс-палиндром.

Для этого поступим аналогично алгоритму Ахо-Корасик: будем поддерживать для каждого палиндрома суффиксную ссылку \(l(v)\), ведущую из \(v\) в её наибольший суффикс-палиндром. При добавлении очередного символа, будем подниматься по суффиксным ссылкам, пока не найдём вершину, из которой можно совершить нужный переход.

Если в подходящей вершине этого перехода не существовало, то нужно создать новую вершину, и для неё тоже понадобится своя суффиксная ссылка. Чтобы найти её, будем продолжать подниматься по суффиксным ссылкам предыдущего суффикс-палиндрома, пока не найдём второе такое место, которое мы можем дополнить символом \(c\).

Здесь мы использовали обычный массив для хранения переходов. Как и для любых префиксных деревьев, вместо него можно использовтать бинарное дерево поиска, хэш-таблицу, односвязный список и другие структуры, позволяющие обменять время на память, немного изменив асимптотику.

Асимптотика

Покажем линейность алгоритма. Рассмотрим длину наибольшего суффикс-палиндрома строки. Каждый новый символ увеличивает её не более, чем на 2. При этом каждый переход по суффиксной ссылке уменьшает её, поэтому нахождение первого суффикс-палиндрома амортизировано работает за линейное время.

Аналогичными рассуждениями о длине второго суффикс-палиндрома (его длина увеличивается тоже не более, чем на 2) получаем, что пересчёт суффиксных ссылок при создании новых вершин тоже суммарно работает за линейное время.

Алгоритм Манакера

Пусть есть строка \(s\) и мы хотим найти в ней все подпалиндромы.

Мы сразу сталкиваемся с очевидной трудностью: их в строке может быть \(O(n^2)\), что можно видеть на примере строки \(s = aa \ldots a\). Поэтому будем использовать следующий формат: для каждой позиции \(s_i\) найдём наибольший палиндром, центр которого совпадает с \(s_i\) (чётные и нечётные палиндромы будем рассматривать отдельно). Половину его длины, округлённую вниз, будем называть радиусом.

Наивное решение — перебрать \(s_i\), а для него вторым циклом находить наибольшую искомую длину:

Тот же пример \(s = aa\dots a\) показывает, что данная реализация работает за \(O(n^2)\).

Для оптимизации применим идею, знакомую из алгоритма z-функции: при инициализации \(t_i\) будем пользоваться уже посчитанными \(t\). А именно, будем поддерживать \((l, r)\) — интервал, соответствующий самому правому из найденных подпалиндромов. Тогда мы можем сказать, что часть наибольшего палиндрома с центром в \(s_i\), которая лежит внутри \(s_{l:r}\), имеет радиус хотя бы \(\min(r-i, \; t_{l+r-i})\). Первая величина равна длине, дальше которой произошел бы выход за пределы \(s_{l:r}\), а вторая — значению радиуса в позиции, зеркальной относительно центра палиндрома \(s_{l:r}\).

Так же, как и z-функция, алгоритм работает за линейное время: цикл запускается только когда \(t_i = r — i\) (иначе палиндром уже во что-то упёрся), и каждая его итерация сдвигает увеличивает \(r\) на единицу. Так как \(r \leq n\), получаем, что суммарно эти циклы сделают \(O(n)\) итераций.

Для случая чётных палиндромов меняется только индексация:

Также можно было не писать отдельно две реализации, а воспользоваться следующим трюком — сделать замену:

\

Теперь нечётные палиндромы с центром в \(s_i\) соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в \(\#\) — чётным.

Палиндромы вне литературы

На самом деле, палиндромия свойственна не только тексту. Это явление применимо к любому набору символов, отвечающих главному критерию. А именно, идентичности чтения, вне зависимости, с какой стороны начинать.

Математика

Математические перевертыши также называют числовыми. Исходя из определения, они представляют собой симметричный цифровой ряд.

Количество цифр в нем может быть как четным, так и нечетным. Нахождение и манипуляции с такими натуральными числами пользуются большой популярностью среди теоретиков математики.

Биология

Поразительным открытием стало то, что палиндромы можно буквально отыскать в каждом из нас. Сделать это можно, расшифровав структуру ДНК.

Размер последовательности достаточна для существования миллиона симметричных фрагментов разной длинны.

Информатика

Активное развитие информационных технологий многократно упростило задачу нахождения симметричных комбинаций знаков в тексте и цифровых рядах.

Написанные для этого алгоритмы путем перебора могут отыскать за несколько минут примеры, над которыми людям пришлось бы трудиться годами. Решение таких задач применяется при обучении программированию.

Музыка

Палиндромы возможны даже в музыке. Произведения считаются таковыми, если их нотное написание симметрично относительно центра мелодии.

В таком случае, вне зависимости от того, с какой стороны начать играть по нотам, музыка будет звучать одинаково. В свое время с этим успешно экспериментировали Моцарт, Мошелес и Хиндемит.