Как составить фразу палиндром

Что такое палиндром. Примеры палиндромов (перевертышей) для детей начальной школы: слова и фразы. Палиндром из учебника по русскому языку с ответом, 2 класс.

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

Во втором классе дочери задали по русскому языку интересное домашнее задание (учебник В.П. Канакиной и В.Г.Горецкого “Русский язык. 2 класс. Часть 1” стр. 84 упр. 128).

Чем же оно интересно?

В этом задании дети знакомятся с тем, что такое палиндром, и одним из примеров наиболее известной фразы – палиндрома.

В детстве я выписывала палиндромы в блокнот, ведь это такие необычные слова и предложения! В древности люди даже считали их магическими. Сейчас эти слова и фразы нетрудно найти в интернете (правда, многие предложения могут содержать не совсем литературные слова).

128. Прочитайте.

Палиндром – это слово или сочетание слов, одинаково читающееся слева направо и справа налево.
Вот знаменитый палиндром поэта А. Фета:
А роза упала на лапу Азора.

• Попробуйте составить палиндром из данных слов.
  Кабан, баклажан, нажал, на.
• Запишите составленный палиндром.

 

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

В России палиндромы еще называли рачьими песнями (из-за того, что раки умеют передвигаться задом наперед) и перевертышами. Они одинаково читаются в обе стороны без учета пробелов и знаков препинания.

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

Слова – перевертыши (палиндромы). Примеры

Примеры некоторых слов – перевертышей (палиндромов).

Есть даже имена – палиндромы: Анна, Алла.

Фразы – палиндромы. Примеры

Наверное, самая известная фраза (предложение) палиндром – это приведенная в упражнении в качестве примера фраза Афанасия Фета. Известна она стала благодаря тому, что ее писал Буратино под диктовку Мальвины в “Золотом ключике” Алексея Толстого.

В кроссвордах и сканврордах даже попадается такое задание: “Пес из палиндрома (4 буквы)”. Имеется в виду именно эта фраза, а имя пса – Азор.

Примеры фраз – палиндромов.

Для закрепления темы можно поиграть: несколько участников за определенное время пишут все слова-перевертыши или предложения-перевертыши, которые смогут вспомнить.

Разновидности палиндромов

У палиндромов есть несколько разновидностей. В одной из них слово повторяется, но читать его нужно не наоборот, а с определенного места. Например, предложите ребенку стать волшебником и превратить одно слово в другое. Пусть ребенок много раз подряд вслух повторит слово “кабан”. Какое совсем другое слово он услышит?

Кабанкабан – банка.

А если, наоборот, повторять вслух слово “банка”, то можно услышать слово “кабан”.

Еще несколько таких слов: цоколь и кольцо, мышка и камыш.

Палиндром из слов “кабан”, “баклажан”, “нажал”, “на”

Теперь самостоятельно составить палиндром из слов “кабан”, “баклажан”, “нажал”, “на” ребенку будет несложно: нужно попробовать составить фразу из этих слов и проверить, читается ли она справа налево также, как и слева направо. Если нет, переставить слова местами и проверить еще раз.

Вообще существует два способа составить палиндром из этих слов:

• Нажал кабан на баклажан.
• На баклажан нажал кабан.

Из них наиболее известна первая фраза.

Предлагаю также посмотреть другие статьи из рубрики «Школьные задания».

© Юлия Шерстюк, https://moreidey.ru

специально для gwean и mym_kak_mym
Лена набила рожу мужу – муж орал и банан ел. (Михаил Фельдман)

1. Допустим, что исходное слово при построении палиндрома Лена.

2. Запишем его дважды одно под другим в две строки:

         Лена

         Лена

3. Первую строчку прочитаем как обычно – слева направо: Лена, а вторую в обратном порядке – справа налево (бустрофедон, «ходом быка», как читали древние греки): анел.

4. Соберем все в одно целое, читая теперь уже только слева направо в одну строчку: Лена … анел.

5. Если левая часть (аверс) – исходное слово – была осмысленна изначально: Лена, то правая (реверс) получилась явно бессмысленной: анел.

6. Попробуем выделить в реверсе осмысленные слова («материализовать» слова): -ан [ел].

7. Сборка: Лена … – ан ел.

8. Согласовывая Субъект Лена и Предикат ел – получим: Лена … ел(а).

9. Соответственно согласованная флексия -а симметрично породит союз А в начале Предложения в общем случае: А Лена … -ан ел(а), или слово, начинающееся на А-, если повезет: Алена … -ан ел(а)

10. Если исходить из семантической матрицы Предложения SVO: Субъект Предикат(глагол) Объект, то здесь заполнены только 2 места – SV, а место Объекта (Лена ела Что?) свободно.

11. Материализуем Объект: А Лена … БАНан ел(а).

12. Тогда слева возникает паразитный морф НАБ-.

13. В нем сразу же материализуется [НА] = 1) предлог на или 2) префикс на-.

14. Далее возникает альтернатива: 1) остаться в пределах одного простого Предложения SVO, выбрав предлог на, задающий косвенный падеж периферийного участника, что-то типа А Лена НА БОКУ/ БАЗАРЕ /БИДЕ … БАНан ела (Ср.: А Лена на боку, суко!, банан ела!) или 2) выбрав префикс на-, ввести новый Предикат и тем самым перейти к сложному Предложению  SVO1- SVO2 или  хотя бы причастному обороту SVO1,VO2 (Ср.: А Лена, набрав чвар, банан ела!).

15. Если выбран второй Предикат наб-, первоначальное Предложение разрушается и возникает 2 новых: А Лена НАБИЛА … -АЛ И БАНан ел(а) с незаполненными ячейками семантической матрицы: SV?1… ?OV2.

16. Что же такое набила Лена? Первое, что приходит в голову – идиома Набила морду! (Ср.: Лена, набила рот – оря, рот орал – и банан ел!).

17. Поскольку ничего путного при обратном чтении не материализуется, попробуем синоним морду=рожу: Набила рожу!

18. Сборка: А Лена набила рожу… уж орал и банан ел(а).

19. Поскольку явно намечаются однородные предикаты орал и ел в левой части, проведем рассогласование – уберем флексию -а и соответственно уйдет союз А слева: Лена набила рожу… уж орал и банан ел.

20. В первом Предложении не хватает только Адресата (набила рожу Кому?). Если Субъектом второго Предложения считать ужа, то конечно – ужу! Тем более что это просто пробка в дырке челюстно-лицевого палиндрома.

21. Сборка: Лена набила рожу ужу, уж орал и банан ел.

22. Но тут есть противоречие: рожа – неприятное лицо, а лицо только у человека, а у ужа – морда, да и орать он может только чисто метонимически-метафорически (издавал звук), скорее – шипел, и не факт еще, что ужи питаются бананами! Да и как можно набить маленькую мордочку ужа,  да и чем? Тут налицо разные семантические миры!

23. Слава богу, что центр палиндрома можно заполнить добавлением одной согласной (материализовать слово Муж), и соответственно Адресатом будет Мужу, что сразу же исправляет семантический мир: у мужа и [жена] Лена, и рожа, которую легко набить, так, что он будет орать, да и банан – вполне его еда.

24. Сборка: Лена набила рожу мужу, муж орал – и банан ел.

25. А полная семантическая экспликация: [Жена] Лена набила рожу [своему]  мужу, [в результате чего] муж орал – и [потом] банан ел.

26. Если отключиться от конкретики, то в Предложении кроме Субъект-Предикат-Объектных отношений выражаются отношения Родства, Принадлежности, Причины-Следствия, Следования.

27. Т.о. вырисовываются семантические приемы построения палиндрома: бустрофедон, сборка, материализация слова, согласование, рассогласование, заполнение семантической матрицы простого предложения SVO, преобразование одной группы  SVO простого предложения в несколько групп SVO1,  SVO2 и т.д. сложного предложения, идиомы, синонимы, однородные члены, поиск периферийных участников при заполненной матрице SVO, однородный семантический мир, образность.

28. Но м.б. есть смысл идти от предикатов (глаголов)? Если здесь идти от фразы: набила рожу мужу, или хотя бы устойчивой синтагмы набила рожу, то это автоматически породит всю фразу: 1) набила рожу …; 2) набила рожу … Муж орал и бан-; 3) ЛЕНА набила рожу … Муж орал и банАН ЕЛ; 4) Лена набила рожу МУЖУ муж орал и банан ел.

Палиндром — это не болезнь, это очень интересно…

ПАЛИНДРОМЫ (перевертыши) — слова, читающиеся одинаково в обоих направлениях. Самым длинным в мире палиндромом принято считать финское слово SAIPPUAKIVIKAUPPIAS (торговец щелоком). В английском языке, насколько мне известно, самое длинное из этого типа — REDIVIDER (что-то вроде перегородки).

Некоторые примеры палиндромов в русском языке:

АЗИЗА Имя.

ДОВОД Аргумент.

КАБАК

КАЗАК

КОТОК Котик.

ПОТОП

ШАБАШ Гулянка нечисти.

А ВОТ ОЧЕНЬ ИНТЕРЕСНО! Некоторые палиндромные фразы:

• Аргентина манит негра.
• На в лоб, болван!
• Умер, и мир ему.
• Лезу на санузел.
• У дуба буду.
• Oколо Миши молоко.
• Морда казака за кадром.
• Венер хотят охренев.
• Вот сила типа капиталистов.
• Летя, догонит Иного дятел
• Ешь немытого ты меньше!
• Откопать тапок-то?
• «Пустите!» — Летит супу миска Максиму. — «Пустите, летит суп!»
• А щётка – как тёща!
• Я не реву — уверен я.
• А муза рада музе без ума да разума.
• Кулинар, храни лук.
• Ты, милок, иди яром: у дороги мина, за дорогой огород, а за ним и город у моря; иди, коли мыт.
• Он в аду давно.
• Ого, вижу живого.
• Коту скоро сорок суток.
• Не женат, а нежен.
• Ты моден и недомыт.
• Оно, лосося мясо, солоно.
• Веер веял для евреев.
• Я с леди все же свиделся.
• Мак чужд жучкам.
• Дорого небо, да надобен огород.
• Леша на полке клопа нашел.
• Меня истина манит сияньем.
• Надо меч в кулак, а лук — в чемодан.
• Шорох от дубка как будто хорош.
• Не видно, как он дивен.
• А в Енисее — синева.
• Я сличил то и то — вот и отличился.
• Лидер бодро, гордо бредил.
• Я умру, хлебороб, – ел хурму я.
• И мал Иван, а лупил у лип улана вилами!

1. Самый короткий палиндром в русском языке состоит из одной буквы — «О!».
2. Интересно двустишие Д. Авалиани, написанное гомеровским гекзаметром (2 строчки — 2 перевертыша): Море могуче. В тон ему, шумен отвечу Гомером: ‘Море, веру буди — ярок, скор я иду буревером’
3. Древнейший из сохранившихся палиндромов написан на латыни и датируется 4 в. н.э. Это фраза «Sator Arepo tenet opera rotas», что означает «Сеятель Арепо с трудом держит колёса».

Обычно записывают ее в форме квадрата:

S A T O R
A R E P O
T E N E T
O P E R A
R O T A S

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

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

Разновидности палиндромов

У палиндромов есть несколько разновидностей. В одной из них слово повторяется, но читать его нужно не наоборот, а с определенного места. Например, предложите ребенку стать волшебником и превратить одно слово в другое. Пусть ребенок много раз подряд вслух повторит слово «кабан». Какое совсем другое слово он услышит?

Кабанкабан — банка.

А если, наоборот, повторять вслух слово «банка», то можно услышать слово «кабан».

Еще несколько таких слов: цоколь и кольцо, мышка и камыш.

Фразы — палиндромы. Примеры

Наверное, самая известная фраза (предложение) палиндром — это приведенная в упражнении в качестве примера фраза Афанасия Фета. Известна она стала благодаря тому, что ее писал Буратино под диктовку Мальвины в «Золотом ключике» Алексея Толстого.

В кроссвордах и сканврордах даже попадается такое задание: «Пес из палиндрома (4 буквы)». Имеется в виду именно эта фраза, а имя пса — Азор.

Примеры фраз — палиндромов.

Для закрепления темы можно поиграть: несколько участников за определенное время пишут все слова-перевертыши или предложения-перевертыши, которые смогут вспомнить.

Фразы, одинаково читаемые с двух сторон! Палиндромы.

Фразы, одинаково читаемые с двух сторон! :)Палиндромы.

А ВЕРА РЕВА
А ВРЕТ СТЕРВА
А К ПОРТУ ТРОПКА
А ЛЕВУ АЛЛА УВЕЛА
А ЛЕС У СЕЛА
А РОЗА УПАЛА HА ЛАПУ АЗОРА (Бурратино)
А ТЫ САМА СЫТА
АДА РЕКЕ РАДА
АКИ ЛЕВ ВЕЛИКА (О России)
АМОС ИЩЕТ У ТЕЩИ СОМА
АРГЕHТИHА МАHИТ HЕГРА
БЕЛ ХЛЕБ
БУКВ КУБ
ВАКУЛА ЛУКАВ
ВЕЛИК ОБОРИH ОH И РОБОК И ЛЕВ
ВОДОВОЗУ РУКУ КУКУРУЗОВОДОВ
ВОЛГУ ДИВ HЕСЕТ ТЕСЕH ВИД УГЛОВ
ВОР ВЛЕТЕЛ В РОВ
ГОЛОД ДОЛОГ
ГОРОД МАССАМ ДОРОГ
ДАРЯ Я РАД
ДИВЕH МHЕ ВИД
ДОМ МОД
ЕЛКА СКАЛА К САКЛЕ
ЗОЛ И БОГ ЛИШИЛ ГОБИ ЛОЗ
ЗОЛОТО ЛОЗ

И ЛИС ОHИ HОСИЛИ
И HЕТ ТЕHИ
ИСКАТЬ ТАКСИ
ИШАКУ КАЗАК СЕHО HЕС КАЗАКУ КАШИ
ИЩИ HИЛ БЛИH И ЩИ
ИЩУ КУЩИ
КИHЬ ЛЕД ЗЕБРЕ БОБЕР БЕЗДЕЛЬHИК
КИРИЛ ЛИРИК
КОВАЛ ПОП ПОПЛАВОК
КОЛЕТ КАЗАК ТЕЛОК
КОHУС И РИСУHОК
КОСТЕР ПРЕТ СОК
КРЮК ЮРК
ЛИХ БАРОH HО РАБ ХИЛ
МИЛ КЛИМ
МОЖЕТ РЕЧЬ ЧЕРТЕЖОМ
МОРОЗ УЗОРОМ
МОТОК С КОТОМ
МЫ HИЗАРИ ЛЕТЕЛИ РАЗИHЫМ
МЫЛО ГОЛЫМ
HА БАКЕ КАБАH
HАЖАЛ КАБАH HА БАКЛАЖАH
HАМ УТРО ГОР ТУМАH
HЕ СУК ВКУСЕH

HЕHЕЦ ЦЕHЕH
Я ОКО ПОКОЯ
ЛИХ БАРОH HО РАБ ХИЛ
ЛОМ О СМОКИHГИ ГHИ КОМСОМОЛ
HО HЕВИДИМ АРХАHГЕЛ ЛЕГ HА ХРАМ И ДИВЕH ОH
О МИМО МИМО
ОКО В ОКО
ОСЕЛО КОЛЕСО
ПИЛ ВИHО ОH И ВЛИП
РАГУ У БАР А РАБУ УГАР
СЕHЯ ЛИПУ КУПИЛ Я HЕС
ТЕРПКО СОК ПРЕТ
ТЕЧЕТ МОРЕ HЕ РОМ ТЕЧЕТ
ТИHА МАHИТ
ТИТ РЕЧЬ ЧЕРТИТ
ТИТУШКА ТАК ШУТИТ
ТО HЕ ТОТ ЕHОТ
ТУТ КАК ТУТ
ТЫ СЫТ
ТЮЛЕHЬ HЕ ЛЮТ
УВЕЛ ДЕД ЛЕВУ
УЖ РЕДКО РУКОЮ ОКУРОК ДЕРЖУ
УHИЗИЛИ ЗИHУ
УПЕР ТИТ РЕПУ
УТРО ВО РТУ
ХИЛ ВОРОH А HОРОВ ЛИХ
ЮРЕ ВЕРЮ
Я ЕМ ЗМЕЯ
Я И ЛИЛИЯ
Я И HЕ ЖИВ ДО ДВИЖЕHИЯ
Я ИДУ С МЕЧЕМ СУДИЯ (Державин)
Я HЕ ЖДУ ССУД ЖЕHЯ
Я HЕ РЕВУ УВЕРЕH Я
Я ОКО ПОКОЯ
Я РАД ДАРЯ
Я РАЗУМУ УМУ ЗАРЯ (Державин)
MADAM, I´M ADAM

Палиндром из слов «кабан», «баклажан», «нажал», «на»

Теперь самостоятельно составить палиндром из слов «кабан», «баклажан», «нажал», «на» ребенку будет несложно: нужно попробовать составить фразу из этих слов и проверить, читается ли она справа налево также, как и слева направо. Если нет, переставить слова местами и проверить еще раз.

Вообще существует два способа составить палиндром из этих слов:

• Нажал кабан на баклажан.
• На баклажан нажал кабан.

Из них наиболее известна первая фраза.

Игра Перевертыши

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

Играть в нее можно и когда все сидят за столом, и на ходу. И возраст игроков в одной команде может быть совершенно разным. В нее с удовольствием играют и взрослые и дети.

Цель игры — перевернуть фразу из Перевертыша в первоначальную, или наоборот, сделать переворот фразы из известной всем в Перевертыш. Как это делается:

1. слова, к которым можно подобать антоним, заменяются на него.
2. остальные слова, к которым подобрать антоним нет возможности, меняются на противоположное с точки зрения игрока. Например: какой антоним к слову Каша? Кто-то скажет — Суп, кто-то — Торт, а третий придумает что-то свое. Или как заменить предлог «с» на «из» или «на» или что-то другое?

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

Реквизит

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

Ход игры

Все участники игры делятся на две команды. Ведущий раздает одной команде Перевертыши, а другой команде исходные фразы. Задача каждой команды перевернуть фразы. Первая команда должна угадать исходную фразу, вторая — придумать свой вариант Перевертыша.

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

Приведу примеры некоторых перевертышей Пословиц

Игра про «перевернутые» названия известных книг:

• Кастрюлька супа (Горшочек каши)
• Редиска (Репка)
• Курочка — железный клювик (Петушок — золотой гребешок)
• Милый лебедь (Гадкий утенок)
• Синяя бейсболка или Оранжевый платочек (Красная шапочка)
• Квадратик (Колобок)
• Мышка в босоножках (Кот в сапогах)
• Головастик-домосед (Лягушка-путешественница)
• Собачья ностиница (Кошкин дом)
• Дождливый король (Снежная королева)
• Чернодождик и 2 великана (Белоснежка и 7 гномов)
• Барашек-Прямоспинка (Конек-горбунок)
• Трусливая швея (Храбрый портняжка)
• Рабыня-жаба (Царевна-лягушка)
• По рачьей просьбе (По щучьему велению)
• Еросинья глупенькая (Елена Премудрая)
• Жарилко (Морозко)
• Принц в тыкве (принцесса на горошине)
• Медная отмычка (Золотой ключик)
• Бодрствующее чудовище (Спящая красавица)
• Великан-уши (Карлик-нос)
• Сажечка (Золушка)
• Одетый горожанин (Голый король)
• Серенькая травинка (Аленький цветочек)
• Толстяк Уязвимый (Кощей Бессмертный)
• Километровочка (Дюймовочка)
• Джимми Короткий носок (Пеппи длинный чулок)
• Томсон, который работает в подвале (Карлсон, который живет на крыше)
• Петушок одноцветный (Курочка Ряба)
• Дворец (Теремок)
• Пациент Ойздоров (Доктор Айболит)
• Петр Крестьяныч и белый заяц (Иван Царевич и серый волк)
• Повесть про найденные часы (Сказка о потерянном времени)
• Принц-Хохотун (Царевна-Несмеяна)
• Иринушка-умница (Иванушка-дурачок)
• Лондонские танцоры (Бременские музыканты)
• История про живую крестьянку с 14 слабаками (Сказка о мертвой царевне и семи богатырях)
• Знайка под Землей (Незнайка на Луне)
• Напрямик тенью в 10 ночей (Вокруг света за 80 дней)
• Салатовый огород (Вишневый сад)
• Континент безделушек (Остров сокровищ)
• Принесенные штилем (Унесенные ветром)
• Счастье в глупости (Горе от ума)
• Закон и поощрение (Преступление и наказание)
• Фиолетовые бакенбарды (Синяя борода)
• Пешеход с ногами (Всадник без головы)
• Матери и родители (Отцы и дети)
• Живые тела (Мертвые души)
• Громкая Волга (Тихий Дон)
• Кошачья печень (Собачье сердце)
• Бабка и пустыня (Старик и море)
• Два миллиона километров над землей (Двадцать тысяч лье под водой)

Оригинальные рисунки перевертыши (60 картинок)

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

Мужик с бородой

Голова девушки

Женщина-мужчина

Ребенок в одежде

Огромные глаза

Лошадь Портрет

Тетя-дядя

Повар

Разный мужчина

Филин

Две подруги

Кудрявая голова

С короной на голове

Усатый дядька

Мужчина-женщина

Девушка с крыльями

Бабушка

Дед

Девушка со стрелой

Бульдог

Косынка в горох

Грустная женщина

Крючок и попугай

Старуха и королева

Мужчина

Девушка

Шут

Корабль

Портрет

Щенок с косточкой

Заяц Грустный и веселый

В фуражке

Необычные лица

Слон

Утка

Разные лица

Перевертыши

Перевернутые картинки

Картинка-перевертыш

В каске

Торчащие волосы

Король

Найди 5 отличий

Лев и свинья

Служивый

Кудрявые волосы

Длинный нос

Маски

Красавица

Натюрморт

Встретились и выпили

Рисунок

В пилотке

Что то в клюве

Портрет мужчины

Лицо

Схема

Ромашки на голове

Картинки — перевертыши (Наши увлечения)

Картинки — перевертыши

Перевёртыш вид оптической иллюзии, в которой от направления взгляда зависит характер воспринимаемого объекта.иллюзий .

Перевертыш — одна из самых красивых и забавных оптических иллюзий.

Перевертыш -одна из самых красивых и забавных оптических иллюзий. Вы смотрите на него и видите вполне осмысленный рисунок. Но если вы перевернете картинку на 180 градусов, то вместо ожидаемого перевернутого изображения, вы увидите совершенно другой рисунок!!!

Помогло?

vector<int> pal_array(string s) {
    int n = s.size();

    // окружим строку спецсимволами, чтобы не рассматривать выход за границы
    s = "#" + s + "$";

    // в этом массиве будем хранить расстояние от центра до границы палиндрома
    vector<int> t(n, 0);

    for(int i = 1; i <= n; i++)
        while (s[i - t[i - 1]] == s[i + t[i - 1]])
            r[i-1]++;

    return r;
}

vector<int> manacher_odd(string s) {
    int n = (int) s.size();
    vector<int> d(n, 1);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            d[i] = min(r - i + 1, d[l + r - i]);
        while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}

vector<int> manacher_even(string s) {
    int n = (int) s.size();
    vector<int> d(n, 0);
    int l = -1, r = -1;
    for (int i = 0; i < n - 1; i++) {
        if (i < r)
            d[i] = min(r - i, d[l + r - i - 1]);
        while (i - d[i] >= 0 && i + d[i] + 1 < n && s[i - d[i]] == s[i + d[i] + 1])
            d[i]++;
        if (i + d[i] > r)
            l = i - d[i] + 1, r = i + d[i];
    }
    return d;
}

const int maxn = 1e5, k = 26;

int s[maxn], len[maxn], link[maxn], to[maxn][k];

int n, last, sz;

void init() {
    s[n++] = -1;
    link[0] = 1;
    len[1] = -1;
    sz = 2;
}

int get_link(int v) {
    while (s[n-len[v]-2] != s[n-1])
        v = link[v];
    return v;
}

void add_char(int c) {
    s[n++] = c;
    last = get_link(last);
    if (!to[last][c]) {
        len[sz] = len[last] + 2;
        link[sz] = to[get_link(link[last])][c];
        to[last][c] = sz++;
    }
    last = to[last][c];
}

АТАТА: распутываем задачу про палиндром

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

Продолжение под катом.

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

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, слово «АТАТА» — это палиндром, а вот слово «АЙАЙАЙ» — нет.

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

Известный кинематографический палиндром — название вышедшего в 2020 году фильма «Довод» (англ. «Tenet»). Русская адаптация в каком-то плане уникальна, потому что у нас нашлась подходящая альтернатива слову «tenet», которая тоже является палиндромом. На многих других языках (в том числе славянских) название фильма оставили как есть. Например, на украинском это «ТЕНЕТ» (Википедия).

Постановка задачи

Итак, задача. Подготовьтесь морально.

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

Всё, клубок запутался. Начнём распутывать.

Вот несколько примеров нечётных палиндромов: «ATATA», «KKKKKKKK», «ABA», «ZO».

Рассмотрим подробнее первую строку — АТАТА. Выпишем все её подстроки нечётной длины:

• A, T, A, T, A — однобуквенное слово всегда палиндром
• ATA, TAT, ATA — очевидно, палиндромы
• ATATA — тоже

В слове ZO нет подстрок нечётной длины больше чем в одну букву. И «Z», и «O» — палиндромы, поэтому «ZO» — нечётный палиндром.

Пусть нам дана строка ABCDEF, и мы можем заменить не более одного символа (K=1), чтобы сделать из неё нечётный палиндром. Оптимальным решением было бы, например, заменить первую букву на C, тогда мы получили бы CBCDEF, где длина наибольшей подстроки, являющейся нечётным палиндромом, была бы равна трём (это CBC).

С тем же успехом мы могли бы прийти к варианту ABCFEF.

А вот если изначально у нас была строка ZXXXZ, и опять можно изменить не более одного символа, то надо заменить средний, так как ZXX и XXZ не являются палиндромами. В итоге мы получим ZXZXZ.

Структура нечётного палиндрома

Теперь заметим кое-что в рассмотренных примерах. Все нечётные палиндромы имеют схожую структуру: в них чередуются буквы (или все буквы одинаковые). И это действительно единственная форма, которую имеет нечётный палиндром. Почему это так?

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

На рисунке выше показано, как получается чередующаяся структура строки. Одинаковым цветом выделены одинаковые символы. Сначала посмотрим на палиндром длины 3, который начинается в самом первом символе исходной строки. Тогда 1 и 3 символ можно пометить зеленым. Про 2-й символ пока ничего непонятно. Сдвинем палиндром на единицу вправо, получим, что 2 и 4 символы можно покрасить в один цвет. Так, сдвигаясь каждый раз на единицу, мы получим, что все символы на нечётных позициях зелёные, а на чётных — синие. Более строго можно доказать этот факт с помощью метода математической индукции, например.

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

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

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

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

Наивное решение

Теперь попробуем сделать как можно более длинную хорошую подстроку, которая начинается строго в символе с номером L. Указатель R будет отмечать ту позицию, до которой мы сумели расширить хорошую подстроку. Будем шагать указателем R вправо, начиная от позиции L. На каждом шаге будем учитывать в счётчике символов для чётных и нечётных позиций очередной символ. Прежде чем передвинуть R на шаг вправо, проверим по счётчикам, что сделать подстроку с L до R хорошей можно не более чем за K операций.

Если применить описанные действия независимо для всех L от 0 до n – 1, где n — длина исходной строки, а затем найти наиболее длинную найденную хорошую подстроку, то мы решим задачу. Однако временная сложность данного решения составит O(n^2), так как для каждой позиции L мы сделаем в худшем случае примерно n – L шагов при передвижении R.

Улучшаем асимптотику решения

Мы можем ускорить это решение с помощью техники двух указателей. Не будем обнулять счётчики и сбрасывать позицию R после того, как максимально отошли вправо от L. Переиспользуем текущую информацию при переходе от L к L+1. Для этого надо убрать из счётчиков элемент на позиции L — и всё. Затем можно продолжать делать проверки и отодвигать R вправо до тех пор, пока не исчерпаются K операций изменения элементов.

На рисунке выше показан ход указателей L и R, K=2. Подчёркнутые символы будут изменены при соответствующих L и R

Оценим сложность новой версии алгоритма. Указатель R суммарно сделает не более n шагов вправо, указатель L — тоже. Передвижение указателя сопровождается обновлением счётчиков и проверкой числа изменений для получения хорошей подстроки — эти действия выполняются за константное время, O(1). Таким образом мы получаем сложность O(n).

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

Подробнее про метод двух указателей и про другие интересные приёмы мы рассказываем на курсе «Алгоритмы и структуры данных». Если вам интересна эта тема, приглашаю на наш курс.