Проверка палиндрома

Проверка палиндрома — это проверка симметрии символов или элементов относительно середины. Алгоритм сравнивает первый элемент с последним, второй — с предпоследним и так далее, пока пары не закончатся или не обнаружится различие.

Что такое симметричная последовательность

Сначала полезно повторить устройство строки и последовательности. Строка состоит из символов, а последовательность — из элементов, которые можно получать по индексам. В обоих случаях элементы обычно нумеруются с нуля в программировании: первый имеет индекс \(0\), последний — индекс \(n-1\), где \(n\) — длина последовательности.

Достаточно проверить только первую половину элементов. Вторая половина проверяется одновременно, потому что каждому элементу слева соответствует ровно один элемент справа. Центральный элемент при нечётной длине ни с чем не сравнивается: он симметричен сам себе.

Алгоритм через два указателя

Самый удобный способ — использовать два индекса: левый \(l\) начинает с нуля, правый \(r\) — с \(n-1\). На каждом шаге сравниваются \(a_l\) и \(a_r\). Если они различны, симметрии нет, и алгоритм можно немедленно завершить. Если равны, \(l\) увеличивается на единицу, а \(r\) уменьшается на единицу.

Цикл продолжается, пока \(l<r\). Условие строгое: когда указатели встретились или пересеклись, все необходимые пары уже проверены. Для строки вместо \(a_i\) используются символы \(s[i]\).

1palindrome(a, n):
2    l := 0
3    r := n - 1
4    while l < r:
5        if a[l] != a[r]:
6            return false
7        l := l + 1
8        r := r - 1
9    return true

Проверка строки и последовательности

Для строки алгоритм полностью такой же, как для массива символов. Если в условии требуется учитывать регистр символов, сначала нужно понять, различаются ли A и a. При проверке без учёта регистра строку обычно предварительно приводят к одному регистру.

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

1def is_palindrome(s):
2    left = 0
3    right = len(s) - 1
4    while left < right:
5        if s[left] != s[right]:
6            return False
7        left += 1
8        right -= 1
9    return True

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

Разобранный пример

Если бы на любом шаге символы не совпали, ответ стал бы отрицательным сразу. Например, для ABDCBA первые две пары совпадут, а на третьем сравнении получится \(D\ne C\).

Другие способы и границы применимости

Можно создать обратную копию строки и сравнить её с исходной: \(s=reverse(s)\). Такой способ короткий, но требует дополнительной памяти \(O(n)\). Для экзамена чаще полезнее понимать вариант с двумя указателями: он показывает саму идею симметрии и не создаёт копию.

Для массива чисел сравниваются сами числа, а не их строковое представление. Например, последовательность \([1,2,1]\) — палиндром. Если записать числа как текст, могут появиться другие правила: ведущие нули, пробелы и регистр уже становятся значимыми только по условию.

Связь с другими алгоритмами

Проверка палиндрома — частный случай задач на симметрию. В задачах на чередование проверяются соседние элементы, а здесь — элементы, равноудалённые от краёв. При подсчёте частоты символов важно, сколько раз встречается каждый символ, но частоты сами по себе не доказывают палиндромность: строки aabb и abba имеют одинаковые частоты, хотя первая не является палиндромом.

В задачах ЕГЭ-24 и ЕГЭ-27 важно внимательно читать, что именно требуется: проверить всю строку, найти длину палиндромного фрагмента, обработать несколько последовательностей или вывести число успешных сравнений. Базовый приём остаётся тем же — сопоставление зеркальных позиций.