Палиндром на C: проверяем строку двумя указателями без лишнего копирования

Палиндром — последовательность символов, которая читается одинаково слева направо и справа налево: racecar, madam, level. Проверка строки на палиндром — одна из первых задач, где удобно освоить работу с указателями в C. Классический подход — два указателя, сходящихся к центру, — не требует дополнительного буфера и работает за линейное время.

Идея двух указателей​

Один указатель ставится на начало строки, второй — на последний символ (перед нуль-терминатором). На каждом шаге символы сравниваются: если они равны, оба указателя сдвигаются навстречу друг другу; если нет — строка не палиндром. Цикл завершается, когда указатели встретились или пересеклись.

Это даёт O(n) по времени и O(1) по дополнительной памяти: строка не копируется, не разворачивается, не выделяется ни одного байта сверх входных данных.

Базовая реализация​

#include <stdio.h>
#include <string.h>

int is_palindrome(const char *s)
{
    if (s == NULL)
        return 0;

    size_t len = strlen(s);
    if (len <= 1)
        return 1;

    const char *left  = s;
    const char *right = s + len - 1;

    while (left < right) {
        if (*left != *right)
            return 0;
        left++;
        right--;
    }
    return 1;
}

int main(void)
{
    const char *tests[] = {"racecar", "hello", "madam", "a", "", "abba"};
    size_t n = sizeof(tests) / sizeof(tests[0]);

    for (size_t i = 0; i < n; i++) {
        printf("%-10s -> %s\n", tests[i],
               is_palindrome(tests[i]) ? "palindrome" : "not palindrome");
    }
    return 0;
}

Вывод:

racecar    -> palindrome
hello      -> not palindrome
madam      -> palindrome
a          -> palindrome
           -> palindrome
abba       -> palindrome

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

Пошаговый разбор на примере​

Возьмём строку "abba" (длина 4):

Шаг	left указывает на	right указывает на	Сравнение	Результат
1	s[0] = 'a'	s[3] = 'a'	'a' == 'a'	продолжаем
2	s[1] = 'b'	s[2] = 'b'	'b' == 'b'	продолжаем
3	left >= right	—	цикл завершён	палиндром

Для "hello" (длина 5) первый же шаг даёт 'h' != 'o', и функция сразу возвращает 0.

Расширенная версия: без учёта регистра и не-буквенных символов​

В реальных задачах часто нужно игнорировать пробелы, знаки препинания и регистр. Фраза "A man, a plan, a canal: Panama" — палиндром, если рассматривать только буквы и цифры.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int is_palindrome_extended(const char *s)
{
    if (s == NULL)
        return 0;

    const char *left  = s;
    const char *right = s + strlen(s) - 1;

    while (left < right) {
        /* Пропускаем не-буквенно-цифровые символы слева */
        while (left < right && !isalnum((unsigned char)*left))
            left++;
        /* Пропускаем не-буквенно-цифровые символы справа */
        while (left < right && !isalnum((unsigned char)*right))
            right--;

        if (tolower((unsigned char)*left) != tolower((unsigned char)*right))
            return 0;

        left++;
        right--;
    }
    return 1;
}

int main(void)
{
    const char *phrase = "A man, a plan, a canal: Panama";
    printf("%s\n", is_palindrome_extended(phrase)
           ? "palindrome" : "not palindrome");
    return 0;
}

Здесь isalnum и tolower из <ctype.h> принимают аргумент типа int, поэтому символ приводится к unsigned char, чтобы избежать неопределённого поведения при отрицательных значениях char (актуально для расширенных кодировок).

Почему не стоит разворачивать строку​

Часто начинающие пишут проверку так: копируют строку в буфер, разворачивают копию через strrev (или вручную), затем сравнивают strcmp. Это работает, но:

• Требует O(n) дополнительной памяти.
  
• strrev отсутствует в стандарте C и недоступна на многих платформах.
  
• Копирование и разворот — два прохода по данным вместо одного.
  

Два указателя делают всё за один проход и без аллокаций.

Типичные ошибки​

Выход за границы при пустой строке​

Если strlen(s) возвращает 0, выражение s + len - 1 даёт s - 1 — указатель перед началом массива. Разыменовывать его нельзя. Поэтому проверка len <= 1 стоит до инициализации right.

Сравнение left <= right вместо left < right​

При чётной длине строки указатели никогда не указывают на один и тот же символ — они пересекаются. Условие left < right корректно для обоих случаев. Если написать <=, центральный символ при нечётной длине сравнится сам с собой, что безвредно, но при чётной длине указатели могут выйти за границы после последнего шага.

Забытый const​

Функция не модифицирует строку, поэтому параметр должен быть const char *. Это позволяет передавать строковые литералы без предупреждений компилятора.

Не-ASCII символы​

Обе реализации работают на уровне байтов. Для UTF-8 многобайтовые символы (кириллица, CJK) будут сравниваться побайтово, что формально корректно для проверки палиндрома в UTF-8, но только если строка нормализована (одинаковый порядок комбинирующих символов). Для полноценной работы с Unicode нужна библиотека вроде ICU.

Оценка сложности​

Параметр	Базовая версия	Расширенная версия
Время	O(n)	O(n)
Память	O(1)	O(1)
Количество проходов	1	1

В расширенной версии внутренние циклы while суммарно сдвигают указатели не более чем на n позиций за всё время работы внешнего цикла, поэтому общая сложность остаётся линейной.

Граничные случаи​

Вход	Ожидаемый результат	Пояснение
NULL	0 (не палиндром)	Защита от разыменования нулевого указателя
""	1	Пустая последовательность тривиально палиндромна
"a"	1	Один символ всегда палиндром
"ab"	0	Минимальный не-палиндром
"aa"	1	Два одинаковых символа
Строка из 10⁶ символов	1 или 0	strlen вернёт size_t, переполнения нет на 64-битной платформе

Проверка результата​

Скомпилируйте с предупреждениями и санитайзером, чтобы убедиться в отсутствии ошибок:

gcc -Wall -Wextra -Werror -fsanitize=address,undefined -o palindrom palindrom.c
./palindrom

Если AddressSanitizer и UBSan молчат, а вывод совпадает с ожидаемым — реализация корректна для переданных тестов. Для продакшн-кода добавьте тесты на все граничные случаи из таблицы выше.

Когда двух указателей недостаточно​

Если нужно проверить, является ли подстрока палиндромом, или найти самую длинную палиндромную подстроку, двух указателей в лоб не хватит. Для таких задач применяют:

• Manacher's algorithm — находит все палиндромные подстроки за O(n).
  
• Хеширование (rolling hash) — позволяет проверять произвольные подстроки за O(1) после предподсчёта.
  
• Динамическое программирование — классический подход для самой длинной палиндромной подстроки за O(n²) времени и O(n²) или O(n) памяти.
  

Для простой проверки всей строки целиком два указателя — оптимальный выбор: минимум кода, минимум памяти, один проход.

Источники​

• Palindrome - Wikipedia
  
• Main Page - Algorithms for Competitive Programming