Задачи / Строки / Проверка строки на палиндром

Проверка строки на палиндром: блок-схема и алгоритм

Палиндром читается одинаково слева направо и справа налево: «шалаш», «топот». Сравниваем первый символ с последним, второй с предпоследним и так до середины; при первом несовпадении — не палиндром.

Блок-схема: Проверка строки на палиндром

Алгоритм по шагам

Ввести строку s; i = 1, j = длина(s), p = да.
Пока i < j и p = да: если s[i] ≠ s[j], то p = нет; i = i + 1, j = j − 1.
Если p = да — палиндром, иначе — нет.

Открыть блок-схему в редакторе

Пример работы

Вход	s = «топот»
Шаг 1	т = т
Шаг 2	о = о
Шаг 3	i = 3, j = 3 — дошли до середины
Результат	палиндром

Решение на Python

s = input()
i, j, p = 0, len(s) - 1, True
while i < j and p:
    if s[i] != s[j]:
        p = False
    i += 1
    j -= 1
print("палиндром" if p else "не палиндром")   # коротко: s == s[::-1]

Решение на Pascal

var s: string;
    i, j: integer;
    p: boolean;
begin
  readln(s);
  i := 1; j := length(s); p := true;
  while (i < j) and p do
  begin
    if s[i] <> s[j] then p := false;
    i := i + 1;
    j := j - 1;
  end;
  if p then writeln('палиндром')
  else writeln('не палиндром');
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Проверка на палиндром
начало
ввод s
i = 1
j = длина(s)
p = да
пока i < j и p = да
    если s[i] ≠ s[j]
        p = нет
    i = i + 1
    j = j − 1
если p = да
    вывод «палиндром»
иначе
    вывод «не палиндром»
конец

Сложность

O(n), где n — длина строки; память O(1).

Частые ошибки

Для фраз («А роза упала на лапу Азора») сначала уберите пробелы и приведите буквы к одному регистру.
Цикл до конца строки вместо середины — каждая пара проверяется дважды.
В старых версиях Pascal строка ограничена 255 символами.