Что не является палиндромом
Коллекция палиндромов
Для начала мы хотели бы Вас пригласить на наш чемпионат:
Мы решили собирать коллекцию палиндромов.
Палиндром (от греч. «назад, снова» и греч. — «бег») — слово или текст, одинаково (или почти одинаково) читающиеся в обоих направлениях.
Отдельные палиндромические словосочетания и фразы известны с глубокой древности, когда им зачастую придавался магически-сакральный смысл (не лишена этого оттенка, например, фраза На в лоб, болван, использовавшаяся русскими скоморохами в качестве перформативного высказывания). Авторское творчество в области палиндрома начинается, по-видимому, в Средние века. В русской литературе достоверно известно об авторском палиндромном стихе Державина «Я и;ду съ ме;чемъ судия», затем об авторском палиндромном стихе Фета «А роза упала на лапу Азора». Первую попытку многострочного (и довольно длинного) стихотворного произведения в форме палиндрома предпринял Велимир Хлебников в поэме «Разин». Однако расцвета русский литературный палиндром (преимущественно стихотворный) достиг только в 1970—1990-е года в творчестве Николая Ладыгина, а затем Владимира Гершуни, Елены Кацюбы и Дмитрия Авалиани. В 1990-х годах началось в России и детальное литературоведческое и лингвистическое изучение палиндромии — прежде всего Александром Бубновым и Германом Лукомниковым. Теоретики и практики палиндрома выделили многочисленные пограничные с палиндромом формы: например, оборотень — текст, читающийся слева направо иначе, чем справа налево: «Мир удобен» (Сергей Федин). Среди более редких разновидностей палиндромических текстов следует назвать также слоговые, словесные и фразовые палиндромы, двуязычные палиндромы (в одну сторону текст читается на одном языке, в обратную — на другом) и т. п.. На русском языке наиболее длинным буквенным палиндромом на сегодняшний день является произведение Р. Адрианова «ЦЕН ОКНО», в которой свыше 6 000 букв.
Мы будем Вам благодарны, если Вы добавите свои палиндромы в нашу коллекцию.
Кирилл лирик
Обратите внимание на это уникальное тройное «Л».
АТАТА: распутываем задачу про палиндром
Очень часто авторы алгоритмических задач делают ход конём: они берут задачу с простыми формулировками, заменяют их сложными и непонятными эквивалентами и выдают вам «сложную» задачу. В этом посте мы разберём пример одной такой задачи и обсудим пару полезных для её решения приёмов. Задача будет про палиндром.
Продолжение под катом.
Что такое палиндром
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, слово «АТАТА» — это палиндром, а вот слово «АЙАЙАЙ» — нет.
Пример палиндрома из латинских слов: он составлен таким образом, что в каком бы направлении вы ни начали читать текст, получится одно и то же
Известный кинематографический палиндром — название вышедшего в 2020 году фильма «Довод» (англ. «Tenet»). Русская адаптация в каком-то плане уникальна, потому что у нас нашлась подходящая альтернатива слову «tenet», которая тоже является палиндромом. На многих других языках (в том числе славянских) название фильма оставили как есть. Например, на украинском это «ТЕНЕТ» (Википедия).
Постановка задачи
Нечётным палиндромом будем называть такую строку, у которой все подстроки нечётной длины являются палиндромами. Суть задачи в том, чтобы в данной строке заменить не более K символов так, чтобы максимизировать длину самой длинной подстроки, которая является нечётным палиндромом.
Всё, клубок запутался. Начнём распутывать.
Вот несколько примеров нечётных палиндромов: «ATATA», «KKKKKKKK», «ABA», «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).
Мы выпутались из этой задачи, теперь можно запутываться в какую-нибудь другую.
Подробнее про метод двух указателей и про другие интересные приёмы мы рассказываем на курсе «Алгоритмы и структуры данных». Если вам интересна эта тема, приглашаю на наш курс.
Палиндром. Какие бывают палиндромы?
В русском языке довольно много слов-палиндромов. Приводим их группами по количеству букв.
Палиндромы из 1 буквы
Палиндромы из 2 букв
Палиндромы из 3 букв
Палиндромы из 4 букв
Палиндромы из 5 букв
Палиндромы из 6 букв
Палиндромы из 7 букв
Палиндромы из 9 букв
В сказке А.К.Толстого «Золотой ключик, или приключения Буратино» Мальвина диктовала Буратино палиндром, который тот должен был записать.
Палиндромы из нескольких слов
В разных языках существует огромное количество палиндромов, состоящих из нескольких слов. Короткие фразы-палиндромы, как правило, изящны и заключают в себе некий смысл.
Море могуче. В тон ему, шумен отвечу Гомером:
Палиндромы на иностранных языках
Древнейший из сохранившихся палиндромов написан на латыни и датируется 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
Еще один изящный палиндром, понятный даже без знания инотсранных языков:
«Madam, I’m Adam» («Мадам, я — Адам», — представился первый человек первой женщине)
«Eve» («Ева», — скромно палиндромом ответила она).
Самые длинные палиндромы в мире
В палиндромичном году (2002) Петер Норвиг (англ. Peter Norvig) закончил пятилетнюю работу с применением компьютера по созданию самого длинного палиндрома на английском языке, состоящего из 17 259 слов. Написанная в традициях классического палиндрома A man, a plan, a canal. Panama («Человек, план, канал — Панама»), эта фраза начинается A man, a plan, a cameo, Zena… и заканчивается …Ibanez, OEM, a canal, Panama. К сожалению, в целом этот длиннейший палиндром лишен смысла.
Самый длинный связный роман-палиндром «Olson in Oslo» был написан Лоуренсом Левиным (англ. Lawrence Levine) и состоит из 31 594 слов. Но он труден для чтения из-за применения странных грамматических структур и архаичного языка.
Еще один очень длинный палиндром был составлен Джеральдом Бернсом (англ. Gerald M. Berns), и представляет собой бессмысленный список из 31 358 слов.
А почему бы и Вам, уважаемый читатель, не поиграть самому, с детьми или с друзьями в замечательнейщую игру в слова, фразы и даже большие произведения перевёртыши, то есть
палиндромы?
Исстари бытует мнение, что русский язык не палиндромен, кроме мата и скабрёзности ничего не получается. Это не совсем так. В русском, если поискать, найдутся слова, фразы, предложения палиндромы. Да и самим не так уж и трудно составить что-нибудь этакое палиндромное!
Многим знакомы палиндромичные имена, фамилии и слова из речи или текстов, например:
а так же простые слова и союзы:
— око, кок, кабак, казак, потоп, довод, топот, шалаш, колок, коток*, доход, или, тут, ещё-ещё, еле-еле.
Всем хорошо известен палиндром русского поэта А.Фета:
А роза упала на лапу Азора (вариант его же: «А роза упала не на лапу Азора»)
а так же расхожие словосочетания:
В жизненных ситуациях встречаются очень интересные палиндромы.
Например, ни имя, ни фамилия не являются палиндромами:
Такая же связь может обнаружиться между фамилией и отчеством:
Или всем знакомая фраза, практически ежедневно произносимая:
в которой раздельно слова:
— лезу
— на
— санузел
не являются палиндромами.
И, если каждому покопаться в своей памяти, можно найти уйму подобных примеров.
А теперь задачу несколько усложним.
Для этого нужно попытаться слово прочесть, как обычно, а потом наоборот.
Читали, читали, и попалось слово:
УДАВ.
Прочтём в обратку:
в Аду.
Получили первый палиндром:
Удав в Аду.
А что может быть в Аду? На глаза попалось слово: ЛЕСХОЗ.Вставим его после слова УДАВ.
Получим?
«Удав лесхоз в Аду», но это не палиндром а палиндронт или палиндронат**! Чтобы выражение стало, как требуется, добавим перевёртыш этого слова» ЗОХСЕЛ! Разделим на понятные слова: Зохс ел (Зох сел). Фраза зазвучит, но возникнут дополнительнве вопросы:
Удав Зохс ел лесхоз в Аду!
или
Удав Зох сел лесхоз в Аду!
Получилось осмысленное предложение из 35 букв!
Добавим ещё немного слов для более полного осмысления, получим:
Расширяя текст, добавляя в него различные буквы и слова в прямом и обратном прочтении, можно составить рассказ или даже целый палиндромический роман!
Дерзайте! У Вас всё получится!
***С этим предложением, при желании тоже можно поработать и сделать либо простой палиндром, либо составить палиндромический рассказ.
или ставить с двух сторон от буквы апострофы:
ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА И ИСТОЧНИКИ:
Что такое палиндромы и какие они бывают?
Самый известный палиндром — «А роза упала на лапу Азора». Ну, вы уже вспомнили, что это такое? Кстати, автором этой фразы считается русский поэт XIX века А.А.Фет.
«Жестоко раздумье. Ночное молчанье
Качает виденья былого,
Мерцанье встречает улыбки сурово,
Страданье
Глубоко-глубоко!
Страданье сурово улыбки встречает…
Мерцанье былого виденья качает…
Молчанье. Ночное раздумье жестоко»
(В. Брюсов).
Представляя одну из наиболее трудных форм графической словесной игры, П. появляется спорадически — в позднеантичной поэзии, в поэзии барокко, в поэзии символистов.
Палиндромами писали целые поэмы. Как по мне, то их художественная ценность невелика, но для оттачивания мастерства владения словом — почему бы и нет?
Есть и более сложные ответвления: суперпалиндромы. Самым известным, идущим еще из средних веков, является палиндром-квадрат, который читается вперед, назад, по горизонтали и по вертикали и даже снизу вверх:
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
Эта латинская фраза является игрой слов, но примерный перевод «Пахарь Арепо пашет (работает) по кругу» (sator — пахарь, opera — работать )
В средневековье этот палиндром считался могущественным заклинанием от нечистой силы. Помимо очистительных качеств, Sator Arepo защищал имущество и спящих людей от пожара, причем фраза считалась настолько чудодейственной, что наделялась способностью гасить огонь, если изобразить ее на деревянной дощечке и бросить эту дощечку в пламя. В 1742 году правитель Саксонии издал указ, чтобы в каждом доме держали под рукой такие дощечки — для борьбы с пожарами. Говорят даже, что эта формула входила в гербы пожарных частей в Германии и Лотарингии, наравне с несгораемой рептилией — саламандрой.
В «Египетских тайнах Альберта Великого» рекомендуется использовать этот квадрат для распознавания ведьм, ибо ни одна ведьма не может находиться с ним в одной комнате; для охраны коровьего молока от ведьмовских чар; для исцеления от колик и для защиты от морового поветрия, отравленного воздуха и разнообразного колдовства.
В манускрипте из Бодлианской библиотеки говорится, что с помощью квадрата Сатор можно чудесным образом исполнить любое желание: «Начертай сии слова на пергаменте кровью дикого голубя, и носи их в левой руке, и попроси, о чем хочешь, и ты получишь это». Согласно иным источникам, Sator Arepo, при должной сноровке и дерзости позволял летать по воздуху вороном, орлом или журавлем, даровал невидимость, позволял изменить свой пол, возраст и облик.
В этом заклинании путем перестановки букв находили и священные слова «Pater Noster», Отче наш, и сатанинские высказывания. Средневековье, что ж вы хотите.
А в наше время палиндромы — всего лишь лингвистическая игра. Не сказать, чтобы все они были содержательно глубокими, но некоторым составителям удается создать палиндромы достаточно осмысленные и даже забавные. Вот несколько примеров:
Аргентина манит негра
Ася, молоко около мяса
А щетка как теща
Кит на море — романтик
Но невидим Архангел лег на храм и дивен он
Тропа налево повела, на порт
Туши рано фонари, шут!
Уведи у вора корову и деву
Удавы рвали лавры в аду
Ужас. Ангел лег на сажу
Уж редко рукою окурок держу
Меня истина манит сияньем.
Надо меч в кулак, а лук — в чемодан.
Шорох от дубка как будто хорош.
Тут хорош сыр к еде, крыс шорох тут
И в заключение — еще одна разновидность палиндрома — белый палиндром. Тут я просто приведу заметочку замечательного юмориста и писателя Ллео Каганова, благо она коротенькая, и вы поймете, почему белые палиндромы мне особенно понравились:
_____________________________________________________
Леонид Каганов
клуб ценителей тонкой поэзии
ТЕОРИЯ И ПРАКТИКА БЕЛОГО ПАЛИНДРОМА
Вчера почитал сборник палиндромов Карпова, сел и быстро сочинил тоже несколько. Вот они:
ГHИ HОГУ ГЕОЛОГ
УХО СМЕХА — МЕХИКО
ИЗ УГЛА ЛУК ВОЗИ
УМ МАЛ ДА ТОЛК ЕМУ
ЛОКТЮ HА ЮГЕ КОЛКО
HЕ РАК, А КАРКHЕТ
ЛОМ ОКО ПОЛКА
В ДЕБАГГЕРЕ БАГ HА ДИВО
МАЛ МОДЕМ ДА ЛАМЕР
ТОЛЬКО КОЛ ОКОЛО ЛОТА
СОМ КОВАЛ МОСТ
ША! ДОГ ЛИЛ ГОДОВ КАШУ
БАРАH БАРУ HЕ РАБ
ДУШ В ЖЕЛЕ ДОЛЖHИК
и
ЕШЬ ДРОЖЖИ ЖОПОЙ
Только не надо мне говорить, что, мол, они у меня неправильные и задом-наперед не читаются. Да, не читаются. Вам бы только все задом наперед прочесть! Оно вам нужно? Зато, согласитесь, во всем остальном мои палиндромы ну совершенно ничем не отличаются от обычных! Вон некоторые (не будем показывать пальцами) вообще пишут стихи без рифм и утверждают, что это белый стих. А у меня белый палиндром. Чем он хуже белого стиха?
_____________________________________________
Вот на этой веселой ноте мы и закончим. А вдруг читатели захотят тоже попрактиковаться в составлении палиндромов? желаю успеха!