Палиндром: что это, слова-палиндромы и как проверить свой

Слово «довод» на русском читается одинаково слева направо и справа налево. Ничего необычного, и понятно, почему именно его вспоминают первым, когда говорят про палиндромы. А вот «довод довод» уже не одно слово, а фраза, и палиндромом она становится только после того, как у неё уберут пробел. Эта разница между строгим и нормализованным палиндромом объясняет почти все споры вокруг темы: одни сравнивают символы как есть, другие сначала чистят текст, и оба подхода дают правильный ответ на свой вопрос.

Что такое палиндром: строгое определение

Строго говоря, палиндром это строка, в которой символ на позиции i совпадает с символом на позиции n-1-i для всех i. Иными словами, строка равна своему отражению. Определение не упоминает слова, фразы или язык: оно работает с любыми символами, включая пробелы и знаки препинания, и если строка не совпадает со своей инверсией, палиндромом она не является.

• «дед» три буквы, крайние совпадают, центральная всегда совпадает сама с собой;
• «абба» четыре буквы, первая с последней, вторая с третьей;
• «топот» и «шабаш» по пять букв;
• «ара» короткое слово, симметричное по построению;
• «довод довод» содержит одиннадцать символов вместе с пробелом, поэтому строго палиндромом не является;
• «А роза упала на лапу Азора» тоже не палиндром в строгом смысле: двадцать шесть символов вместе с пробелами, и пробелы не совпадают сами с собой;

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

Нормализация: пробелы, знаки и регистр

Разговорное определение палиндрома гораздо мягче строгого. Никто в жизни не считает, что «А роза упала на лапу Азора» перестаёт быть палиндромом из-за пробелов и заглавных букв. Поэтому перед проверкой текст приводят к сравнимому виду, и важно понимать, что именно при этом убирают.

• пробелы: «довод довод» превращается в «доводдовод», и фраза наконец становится палиндромом;
• знаки препинания: из «А роза упала на лапу Азора» исчезает точка, остаётся «арозаупаланалапуазора»;
• регистр: заглавная «А» в начале и в конце фразы становится строчной, и симметрия проявляется полностью;
• буквы других алфавитов и цифры сохраняются: китайская фраза «上海自來水來自海上» состоит из девяти иероглифов и читается одинаково в обе стороны.

Нормализация не украшение, а часть определения. Если убрать пробелы, но оставить регистр, «А роза упала на лапу Азора» перестанет быть палиндромом: крайние символы окажутся «а» и «А», а это разные символы. Именно поэтому в проверяющих сервисах правила нормализации вынесены в отдельные переключатели, и по умолчанию включены все три.

Слова-палиндромы и классическая фраза

Русских слов-палиндромов немного, но они есть, и некоторые из них вполне обычные. «Дед», «абба», «топот», «шабаш», «ара», «довод», «казак», «ротор», «тот», «мам», «шалаш» — все они совпадают со своей инверсией. Обратная сторона в том, что короткое слово-палиндром находится случайно, а вот палиндромная фраза требует отдельной работы над ритмом и длиной.

дед                 → дед                  (3 символа)
абба                → абба                 (4 символа)
топот               → топот                (5 символов)
шабаш               → шабаш                (5 символов)
довод довод         → доводдовод           (10 символов)
А роза упала на лапу Азора
                    → арозаупаланалапуазора (21 символ)
上海自來水來自海上      → 上海自來水來自海上        (9 символов)

С иероглифами логика та же: символ читается одинаково с двух сторон, а символов нечётное число, значит в центре стоит один символ, совпадающий сам с собой. Проверять такие строки удобно посимвольно: у иероглифа нет формы, которую можно перевернуть, всё держится на порядке знаков.

Проверяем текст: сравнение с концов к центру

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

1. нормализуем строку по выбранным правилам: убираем пробелы и знаки, приводим регистр, если это нужно;
2. ставим левый указатель на первый символ, правый на последний;
3. пока указатели не пересеклись, сравниваем символы слева и справа;
4. при первом несовпадении запоминаем позицию: именно там текст перестал быть симметричным;
5. если все пары совпали, строка палиндром, а одиночный центральный символ всегда совпадает сам с собой.

Шаг 0. Нормализация: убираем пробел → доводдовод (10 символов)

Шаг 1. д vs д   позиции 1 и 10   совпало
Шаг 2. о vs о   позиции 2 и 9    совпало
Шаг 3. в vs в   позиции 3 и 8    совпало
Шаг 4. о vs о   позиции 4 и 7    совпало
Шаг 5. д vs д   позиции 5 и 6    совпало

Указатели сошлись в середине, все пары совпали → палиндром

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

Алгоритм Манакера: все палиндромы за один проход

Сравнение с концов к центру отвечает на вопрос «является ли вся строка палиндромом». Другой вопрос сложнее: «какие палиндромы внутри неё есть». Если проверять каждую подстроку отдельно, работы получится квадратичной: для строки длины n придётся сделать примерно n²/2 сравнений. Алгоритм Манакера находит все палиндромы за линейное время.

Идея в том, что для каждой позиции вычисляется радиус максимального палиндрома с центром в этой позиции. Радиусы нечётных и чётных палиндромов считаются отдельно: в первом случае центр это символ, во втором промежуток между соседними символами. Алгоритм держит правую границу уже найденного палиндрома и, попадая внутрь него, берёт радиус из зеркальной позиции вместо повторных сравнений.

def manacher(s):
    n = len(s)
    d1 = [0] * n          # нечётные палиндромы
    d2 = [0] * n          # чётные палиндромы
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d1[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i-k] == s[i+k]:
            k += 1
        d1[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    l, r = 0, -1
    for i in range(n):
        k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i-k-1] == s[i+k]:
            k += 1
        d2[i] = k
        if i + k - 1 > r:
            l, r = i - k, i + k - 1
    return d1, d2

На строке «abacaba» результат получается таким: нечётные радиусы [1, 2, 1, 4, 1, 2, 1]. Число 4 в центре означает, что вокруг четвёртой буквы помещается палиндром длиной 7, то есть вся строка целиком. Чётные радиусы здесь нулевые: палиндромов чётной длины в «abacaba» нет. По этим двум массивам восстанавливаются все палиндромы: «aba» с позиции 1, «abacaba» с позиции 1 и «aba» с позиции 5.

Зачем это нужно на практике: так ищут палиндромные подстроки в тексте, самая длинная палиндромная подстрока находится за то же линейное время, а проверка «есть ли здесь палиндром» перестаёт быть дорогой даже для текста в десятки тысяч символов.

Палиндромные числа

Число тоже бывает палиндромом, и здесь определение проще всего: цифры читаются одинаково слева направо и справа налево. Однозначные числа палиндромы все. Двузначных девять: 11, 22, 33 и так далее до 99. Трёхзначных уже 90, от 101 до 999, и у каждого крайние цифры совпадают, а средняя может быть любой.

• однозначные: 9 штук, от 1 до 9;
• двузначные: 9 штук, 11, 22, 33, 44, 55, 66, 77, 88, 99;
• трёхзначные: 90 штук, от 101 до 999, по шаблону aba;
• пятизначные: 900 штук по шаблону abcba, от 10001 до 99999, например 12321;
• семизначные: по шаблону abcdcba, самый маленький 1000001.

Пятизначный палиндром записывается как abcba, и проверить любое число можно тем же приёмом с концов к центру. А чтобы увидеть симметрию глазами, помогает переворот текста: перевёрнутое число должно совпасть с исходным.

Палиндромы в ДНК

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

Механика простая: берём последовательность, меняем порядок букв на обратный с учётом парных оснований A к T и G к C, и сравниваем с исходной. Если совпало, перед нами палиндром.

GAATTC
  комплемент:      CTTAAG
  обратный порядок: GAATTC   ← совпало с исходным

GGATCC
  комплемент:      CCTAGG
  обратный порядок: GGATCC   ← совпало с исходным

Правила комплементарности: A↔T, G↔C

Пара GAATTC узнаваема: это сайт, который режет ДНК ферментом EcoRI. Совпадение здесь не случайно, такие последовательности встречаются в природе часто именно потому, что на них сидят ферменты.

Как проверить свой текст

Практическая проверка занимает меньше минуты. Откройте проверку текста на палиндром, вставьте строку и посмотрите результат: сервис скажет, палиндром это или нет, покажет, сколько символов осталось после нормализации, и укажет позицию, на которой символы разошлись. Три переключателя над кнопкой отвечают за правила: игнорировать пробелы, игнорировать знаки препинания, игнорировать регистр.

Рядом пригодятся смена регистра и переворот текста. Полезная связка для проверки: переверните строку и сравните её с исходной, если развертка совпала, перед вами палиндром, а если нет, разворот сразу покажет, где расхождение. Расчёт выполняется в браузере, содержимое поля никуда не отправляется.

Отдельная любопытная деталь: любой шифр, который дважды возвращает исходный текст, сохраняет палиндромы. Так работает шифр Цезаря и ROT13: «abcba» превращается в «nopon», и «nopon» остаётся палиндромом.

Частые вопросы

Является ли пустая строка палиндромом?

Формально пустая строка равна своей инверсии, но в проверяющих сервисах пустой ввод считают непалиндромом и подсказывают, что сначала нужно что-то ввести. Одиночный символ, наоборот, всегда палиндром: сравнивать его попросту не с чем.

Палиндром и анаграмма это одно и то же?

Нет. Анаграмма это перестановка букв, дающая другое слово: «лист» и «слит» анаграммы. Палиндром устроен проще, он совпадает с собой после отражения, поэтому «лист» палиндромом быть не может в принципе.

Правда ли, что палиндромы редки?

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

Помогает ли палиндромный анализ в криптографии?

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

Нужно ли убирать пробелы при проверке?

Зависит от задачи. Если вы проверяете, можно ли сделать слоган или имя визуально симметричным, пробелы и знаки стоит оставить: иначе сравнивается не то, что видит человек. Если вы проверяете симметрию самого набора букв, нормализация обязательна.