Палиндром. Какие бывают палиндромы?
В русском языке довольно много слов-палиндромов. Приводим их группами по количеству букв.
Палиндромы из 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 слов.
Коллекция палиндромов
Для начала мы хотели бы Вас пригласить на наш чемпионат:
Мы решили собирать коллекцию палиндромов.
Палиндром (от греч. «назад, снова» и греч. — «бег») — слово или текст, одинаково (или почти одинаково) читающиеся в обоих направлениях.
Отдельные палиндромические словосочетания и фразы известны с глубокой древности, когда им зачастую придавался магически-сакральный смысл (не лишена этого оттенка, например, фраза На в лоб, болван, использовавшаяся русскими скоморохами в качестве перформативного высказывания). Авторское творчество в области палиндрома начинается, по-видимому, в Средние века. В русской литературе достоверно известно об авторском палиндромном стихе Державина «Я и;ду съ ме;чемъ судия», затем об авторском палиндромном стихе Фета «А роза упала на лапу Азора». Первую попытку многострочного (и довольно длинного) стихотворного произведения в форме палиндрома предпринял Велимир Хлебников в поэме «Разин». Однако расцвета русский литературный палиндром (преимущественно стихотворный) достиг только в 1970—1990-е года в творчестве Николая Ладыгина, а затем Владимира Гершуни, Елены Кацюбы и Дмитрия Авалиани. В 1990-х годах началось в России и детальное литературоведческое и лингвистическое изучение палиндромии — прежде всего Александром Бубновым и Германом Лукомниковым. Теоретики и практики палиндрома выделили многочисленные пограничные с палиндромом формы: например, оборотень — текст, читающийся слева направо иначе, чем справа налево: «Мир удобен» (Сергей Федин). Среди более редких разновидностей палиндромических текстов следует назвать также слоговые, словесные и фразовые палиндромы, двуязычные палиндромы (в одну сторону текст читается на одном языке, в обратную — на другом) и т. п.. На русском языке наиболее длинным буквенным палиндромом на сегодняшний день является произведение Р. Адрианова «ЦЕН ОКНО», в которой свыше 6 000 букв.
Мы будем Вам благодарны, если Вы добавите свои палиндромы в нашу коллекцию.
Кирилл лирик
Обратите внимание на это уникальное тройное «Л».
Синонимы к слову «палиндром»
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я стал чуточку лучше понимать мир эмоций.
Вопрос: сотрапезничать — это что-то нейтральное, положительное или отрицательное?
Связанные слова и выражения
Связанные слова (по тематикам)
Предложения со словом «палиндром»
Значение слова «палиндром»
Отправить комментарий
Дополнительно
Значение слова «палиндром»
Предложения со словом «палиндром»
Высказывалось предположение о том, что простых чисел палиндромов бесконечно много, но эта гипотеза пока не доказана.
Звучит хорошо, но почему-то не прижилось, а везде употребляется слово палиндром.
Прилежащие друг к другу инвертированные повторы образуют палиндромы.
Морфология
Правописание
Карта слов и выражений русского языка
Онлайн-тезаурус с возможностью поиска ассоциаций, синонимов, контекстных связей и примеров предложений к словам и выражениям русского языка.
Справочная информация по склонению имён существительных и прилагательных, спряжению глаголов, а также морфемному строению слов.
Сайт оснащён мощной системой поиска с поддержкой русской морфологии.
Палиндромы и игры-перевертыши: творческие идеи для детей
Палиндром — это не болезнь, это очень интересно…
ПАЛИНДРОМЫ (перевертыши) — слова, читающиеся одинаково в обоих направлениях. Самым длинным в мире палиндромом принято считать финское слово SAIPPUAKIVIKAUPPIAS (торговец щелоком). В английском языке, насколько мне известно, самое длинное из этого типа — REDIVIDER (что-то вроде перегородки).
Некоторые примеры палиндромов в русском языке:
ШАБАШ Гулянка нечисти.
А ВОТ ОЧЕНЬ ИНТЕРЕСНО! Некоторые палиндромные фразы:
Обычно записывают ее в форме квадрата:
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
Палиндром из слов «кабан», «баклажан», «нажал», «на»
Теперь самостоятельно составить палиндром из слов «кабан», «баклажан», «нажал», «на» ребенку будет несложно: нужно попробовать составить фразу из этих слов и проверить, читается ли она справа налево также, как и слева направо. Если нет, переставить слова местами и проверить еще раз.
Вообще существует два способа составить палиндром из этих слов:
Из них наиболее известна первая фраза.
Игра Перевертыши
вспоминаем интересные игры. Одна из любимых мною игр, очень веселая, не требующая практически никакого реквизита, кроме хорошего настроения и фантазии — это игра Перевертыши.
Играть в нее можно и когда все сидят за столом, и на ходу. И возраст игроков в одной команде может быть совершенно разным. В нее с удовольствием играют и взрослые и дети.
Цель игры — перевернуть фразу из Перевертыша в первоначальную, или наоборот, сделать переворот фразы из известной всем в Перевертыш. Как это делается:
Тем и интересна игра, что играть в нее можно на каждом празднике, придумывая к одним и тем же фразам новые Перевертыши. Особенно интересно получаются Перевертыши пословиц — иногда в них звучит очень необычный смысл. Удобно для фраз брать знакомые всем выражения: это могут быть Пословицы, Поговорки, Названия книг, Строчки из стихотворений.
Для этой игры необходимо сделать распечатку тех фраз, которые нужно будет перевернуть. И приготовить бумагу и карандаши.
Все участники игры делятся на две команды. Ведущий раздает одной команде Перевертыши, а другой команде исходные фразы. Задача каждой команды перевернуть фразы. Первая команда должна угадать исходную фразу, вторая — придумать свой вариант Перевертыша.
Играть можно на время, или до последнего справившегося с заданием. После того, как все игроки зачитывают свои варианты, команды меняются ролями. Первой команде раздают исходные фразы, и они придумывают Перевертыши, а вторая команда — угадывают фразы из перевертышей.
Приведу примеры некоторых перевертышей Пословиц
Игра про «перевернутые» названия известных книг:
Оригинальные рисунки перевертыши (60 картинок)
Перевертыши-это забавные картинки. Когда смотришь и видишь уставшую старуху, а когда рисунок перевернешь-то увидишь молодую красивую девушку. С нашей подборкой вы можете провести прекрасно время и поднять себе настроение. Самые оригинальные рисунки перевертыши представлены в этой подборке.
С короной на голове
Девушка с крыльями
Девушка со стрелой
Старуха и королева
Заяц Грустный и веселый
Утка
В каске
Торчащие волосы
Король
Найди 5 отличий
Лев и свинья
Служивый
Кудрявые волосы
Длинный нос
Маски
Красавица
Натюрморт
Встретились и выпили
Рисунок
В пилотке
Что то в клюве
Портрет мужчины
Лицо
Схема
Ромашки на голове
Картинки — перевертыши (Наши увлечения)
Перевертыш — одна из самых красивых и забавных оптических иллюзий.
Алгоритмы для поиска палиндромов
Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке: для чего это нужно, где применяется, как это быстро сделать, какие подводные камни нас ожидают и многое другое. Рассмотрим различные способы для решения данной задачи, выясним плюсы и минусы каждого способа. Эта статья будет обзорной: если я что-то не описываю здесь, то постараюсь всегда дать вам набор ссылок, где всё подробно описано и расписано. Надеюсь, что материал будет интересен как новичкам в сфере алгоритмов, так и матёрым программистам. Что же, если я смог заинтересовать вас, то прошу под кат!
Для начала стоит вспомнить, что же такое палиндром.
Палиндро́м — число (например, 404), буквосочетание, слово или текст, одинаково читающееся в обоих направлениях. Иногда палиндромом называют любой симметричный относительно своей середины набор символов.(выдержка из Википедии)
Определение очень лёгкое и понятное. Мы в данном посте будем рассматривать палиндромы-слова(поп, кок и т.д.). Но это не значит, что алгоритмы неприменимы для иных ситуаций. Просто чуть сузим область.
Для чего может потребоваться искать палиндромы?
На самом деле, не очень то и часто приходится искать палиндромы в повседневной жизни. Уж больно специфичная это задача. Если говорить о строковых алгоритмах, то мы намного чаще встречаем тот же поиск подстроки в строке, чем нахождение количества палиндромов. Поэтому и освещение в литературе намного слабее.
Одно из основных применений — спортивное/олимпиадное программирование. Там задач на такое хватает. Задач понаписывают, а участникам уже думай, каким способом это решить. Из личного опыта скажу, что мне такие задачи встречались всего пару раз, но все они были из разряда «вот тебе задача, ты не думай, а просто напиши алгоритм». То есть не интересные задачи, которые развивают просто механическую память по набиванию алгоритмов.
А более практическое применение нахождения палиндромов — это биологические алгоритмы. Согласно всё той же Википедии и ссылкам снизу Вики, палиндромность биологических соединений играет важную роль на свойствах различных биологических соединений. Я в биологии слаб, поэтому если вам интересно, то вы можете найти более подробную информацию сами.
Отлично, мы выяснили, что мы будем заниматься не совсем бесполезными делами. Давайте же уже перейдем к рассмотрению алгоритмов!
Замечание: во всех нижеприведённых алгоритмах одиночный символ не считается за палиндром. Как вы понимаете, это легко поправить, если одиночные символы тоже нужно будет учесть.
0) Самый банальный алгоритм с асимптотикой O(N^3)
Хочу предупредить сразу, что все исходники будут на C++, и это будут значимые части классов, которые нам могут быть интересны.
Алгоритм самый что ни на есть «лоб»: имеется строка, есть указатель на начало подстроки данной строки, есть указатель на конец данной подстроки. В двух вложенных циклах перебираем границы подстрок и банально проверяем, является ли наша подстрока палиндромом. Ничего сложного.
Но это всё ужасно медленно работает. Почему? Да потому что мы квадрат от N раз (N у нас будет всегда длина строки) перебираем границы текущей подстроки, а потом ещё и за O(N) в худшем случае выполняем проверку для каждой подстроки на палиндромность.
Плюсов у данного способа немного:
+ Легко реализуется. Действительно, оставить багу здесь ну очень сложно.
+ Легко читается. Вы только взглянули, и уже поняли, что да как здесь работает.
+ Малая скрытая константа. Как известно, на время работы алгоритма влияет не только асимптотическая оценка (здесь мы работаем только с худшими случаями), но и скрытая константа. У этого алгоритма скрытая константа крайне мала.
— Крайне малая скорость работы. Как вы можете видеть, что при строке из тысячи букв ‘a’ данный алгоритм сделает порядка 10^9 итераций, что есть очень плохо. А что если строка длиной 100000?
1) Самый банальный алгоритм с асимптотикой O(N^2)
Здесь уже чуточку интереснее. У нас имеется строка, и два временных массива для палиндромов чётной и нечётной длины. А число в ячейке i массива будет хранить количество палиндромов в строке s(исходная строка) с центром в точке i. Для нечётной длины палиндрома центр находится легко, ну а для чётной мы просто чуть поиграемся с индексами и сместим чуточку центр(что видно в коде). Наш результат это есть сумма чисел из двух массивов.
Как видите, снова ничего сложного. Но работает это заметно быстрее предыдущего алгоритма. Почему? Давайте рассмотрим, как же оно всё работает.
Мы бежим по строке, перебирая центральный символ нашего потенциального палиндрома. А потом просто бежим влево и вправо от центрального элемента до тех пор, пока символы одинаковы. Как только они стали разными, это значит, что дальше не будет палиндромов с центром в нашем выбранном элементе, и переходим к следующему.
А работает это быстро на обычных строках очень быстро потому, что наш второй, вложенный цикл, который бежит до тех пор, пока крайние символы равны, обрывается крайне быстро(если предположить, что палиндромов в строке много меньше общего числа подстрок).
Рассмотрим плюсы и минусы способа.
+ Всё также легко кодится. Ошибиться очень сложно.
+ Малая скрытая константа
+ Хорошо ведёт себя на случайных строках
— Всё ещё долгое время работы
После этого способа уже голова начинает думать-думать-думать. И тут идея! А что если мы модифицируем этот способ, только будем от центрального элемента прыгать не на 1 символ с каждой итерацией, а на чуточку больше? И тут нам на помощь приходят…
2) Используем хеши!
Этот способ чуточку сложнее, поэтому сразу приведу код, а потом постараюсь обьяснить, что за магия там творится(хотя магии нет, как вы сами прекрасно знаете):
Краткая суть данного способа: мы перебираем центральный элемент нашего палиндрома, и потом дихотомией стараемся найти наибольший радиус нашего палиндрома (под радиусом здесь понимается расстояние от центрального элемента до крайнего, если у нас палиндром чётной длины, то просто добавим чуточку игры с индексами, чтобы всё работало). Во время подбора мы должны как-то быстро сравнивать подстроки на идентичность. делаем это с помощью хешей. Асимптотика, как легко догадаться: N тратим на перебор центрального элемента, logN в худшем случае тратим на подбор радиуса палиндрома, за единицу сравниваем подстроки с помощью хешей. Итого имеем O(NlogN), что очень даже неплохо на самом деле.
Теперь чуть подробнее остановимся на данном методе.
На чём основывается наш метод? Так как мы перебираем центральный элемент, а потом дихотомией подбираем радиус наибольшего палиндрома с центром в данном элементе, то мы должны быстро брать хеш левой части нашего потенциального палиндрома и сравнивать его с хешем правой части нашего потенциального палиндрома.
Как это сделать? Давайте предварительно рассчитаем хеш для каждого префикса и суффикса исходной строки. В коде это у нас делают методы CountingPrefixHash() и CountingSuffixHash() соответственно.
С помощью методов getHash() и getRevHash() мы можем быстро получить хеши левой и правой частей рассматриваемого на данном этапе потенциального палиндрома. Тут может возникнуть вопрос, почему нельзя воспользоваться одной и той же функцией подсчёта хеша для левой и правой частей. А всё потому, что мы при проверке на палиндромность левую часть мы читаем слева направо, а вторую справа налево. И нам необходимо поддерживать хеш слева направо и справа налево.
Осталась единственная сложность: как сравнить этих 2 хеша? И эту проблему мы решаем с помощью метода isPalindrome(), который приводит хеши к одному основанию и сравнивает их.
Результатом каждой итерации у нас будет количество палиндромов с центром i. Пробегаемся 2 раза для палиндромов чётной и нечётной длины, ответ на нашу задачу есть сумма всех значений массивов oddCount и evenCount
Более подробно про данный метод вы можете почитать в этой статье.
+ Асимптотически мы снизили до NlogN, что не может не радовать. Если брать только худшие случаи, то в теории когда-нибудь мы выиграем
— Довольно тяжело пишется. Легко посеять багу. Нужна немного теоретическая подготовка в области хешей.
— Медленно работает на случайных тестах. Вы можете сами в этом убедиться. А всё из-за большой скрытой константы и из-за того, что даже если у нас нет ни одного палиндрома с центром в данном элементе, то алгоритм сделает logN прыжков, а это всё занимает время.
— Коллизии. Как вы видите, в моём исходнике используется хеш, который обычно пишут на олимпиадах по программированию(да-да, я немного этим когда-то занимался). Так вот, на соревнованиях данный способ показывает себя хорошо. Лично у меня коллизии не случались. Но я знаю про способы спокойно данный хеш завалить(в частности способ с использованием строк Туэ-Морса). Я когда-то слышал, что есть какой-то фиббоначиевый хеш, который вроде бы не ломается на данном тесте, но информация недостоверная. Так что будьте осторожны с коллизиями.
А если мы хотим 100% решение без всякой там коллизийной поправки и ввода хеша по другому основанию и так далее?
3) Алгоритм Манакера
Итак, мы получили с помощью хешей алгоритм за NlogN. Но хочется быстрее. Хочется чего-то линейного. И тут нам на помощь спешит Алгоритм Манакера (по ссылке вы также можете видеть реализацию алгоритма на Java), который мало того, что линеен, так ещё и обладает крайне малой скрытой константой, что положительно сказывается на его скорости работы. Подробно описывать способ я не буду, так как это получится пересказ этой замечательной ссылки (я сам учил алгоритм именно по этой ссылке). Здесь я приведу слегка пересказанное объяснение.
Алгоритм заключается в том, что мы обрабатываем строку символ за символом, поддерживая самый правый палиндром в нашей строке. И на каждой итерации смотрим, наш текущий элемент находится внутри границ самого правого палиндрома или нет. Если находится, то мы можем извлечь ответ из ранее посчитанных значений, путём нехитрых манипуляций с индексами. Если же не находится, то мы идём точно таким же алгоритмом, который описан в пункте 1) этого обзора: идём символ за символом и сравниваем зеркальные элементы относительно центра. Идём до тех пор, пока они равны. И не забываем обновить после этого границы самого правого найденного палиндрома. Это вкратце. Про некоторые подводные камни вы можете почитать в приведённой статье.
Что ещё интересного: во всех задачах, которые я решал на контестах (по олимпиадному программированию), хватало именно этого алгоритма. Очень просто пишется, если ты его писал N раз дома и уже знаешь наизусть.
+ Довольно короткий код.
+ Очень быстро работает. Мало того, что асимптотика O(N), так ещё и малая скрытая константа.
— Идея не такая простая, чтобы самому сходу придумать данный алгоритм
— Можно запутаться во всяких индексах, если проявить невнимательность при написании кода
А есть ли другие способы решить данную задачу за линейное время?
4) Дерево палиндромов
Немного предыстории. Эту относительно новую структуру данных открыл Михаил Рубинчик rumi13 и представил её на Петрозаводских сборах. Структура крайне интересная своей с одной стороны простотой, а с другой тем, что позволяет быстро решать довольно широкий спектр задачи про палиндромы. И самое главное — позволяет довольно просто считать количество палиндромов в строке за O(N) (но само дерево палиндромов думаю придумывалось далеко не для этого, а для более серьёзных задач с палиндромами).
Опять же, перескажу вкратце суть данного алгоритма. С более подробным разъяснением вы можете ознакомиться в этой замечательной статье.
Итак, идея дерева. В вершинах нашего дерева будут находиться только сами палиндромы: ‘a’, ‘b’, ‘aba’ и так далее. Понятно, что сам палиндромы мы не будем хранить, а просто будем хранить из какой вершины мы пришли сюда, и какой символ с двух сторон добавили. Также у нас существуют две фиктивные вершины для удобной реализации алгоритма.
Но как и в любом интересном дереве, у нас также существуют суффиксные ссылки. Суффиксная ссылка будет вести в вершину, которая также является палиндромом (ну потому что у нас в вершинах хранятся только палиндромы) и которая является наибольшим собственным суффиксом данной вершины. То есть из вершины ‘aba’ ссылка будет вести в вершину ‘a’.
Далее, мы по очереди добавляем символы в дерево по одному. И благодаря хитрому устройству дерева и рекурсивной операции добавления (а также суффиксным ссылкам, по которым осуществляется переход), мы обновляем всё дерево.
Это вкратце, подробнее почитайте информацию по ссылке выше (если не боитесь английского)
+ Если Вы ранее работали с деревьями, то вам будет очень просто понять данную идею.
+ Позволяет решать большой спектр задач на палиндромы
— Работает медленнее, чем алгоритм Манакера.
— Можно поставить багу. Но, чисто субъективно, тут это сделать сложнее, чем в том же алгоритме Манакера.
Также стоит упомянуть, что с помощью деревьев существует ещё одно решение данной задачи. Оно заключается в использовании суффиксного дерева и быстрого алгоритма LCA(который работает за препроцессинг O(N) и ответ на запрос O(1). Алгоритм Фарах-Колтон-Бендера). Но он на практике не применяется, так как довольно сложен и у него крайне большая скрытая константа. Представляет скорее академический интерес.
Что может быть ещё интересно про алгоритмы? Правильно, потребление памяти и время работы.
На гитхабе Вы можете скачать также код для тестирования, который генерирует случайные строки и ищет в них палиндромы.
Моё тестирование показало, что ожидаемо алгоритм номер 0 работает крайне медленно. Лидером, как Вы можете догадаться, является алгоритм Манакера. Но что самое интересное: алгоритм с O(N^2) выигрывает с примерно двукратным отрывом у алгоритма с использованием хешей с O(NlogN), что ещё раз доказывает, что не асимптотикой единой меряются алгоритмы. Так происходит из-за особенностей отсечения алгоритма номер 1, и отсутствия оной в способе с хешами. Что касается дерева палиндромов, то оно проигрывает Манакеру в основном из-за операций с памятью, так как приходится выделять память под каждую новую вершину. Но если использовать, например, new с размещением, то разрыв сократится.
Память все алгоритмы потребляют линейно от размера входных данных.
На этом мы завершим наш обзор. Надеюсь, что вы почерпнули для себя хоть что-то новое и вам было хоть чуточку интересно! Все исходники вы можете найти в моём публичном репозитории на Github.
P.S.: Если вы заметили какие-то опечатки, неточности или у вас есть дополнения — прошу отписываться в комментариях и писать в ЛС.
P.P.S.: Смело задавайте вопросы в комментариях — постараюсь ответить, если хватит моей компетенции.
Полезные ссылки, которые могут быть вам интересны после прочтения данной статьи (некоторые ссылки могут повторяться, так как могли проскакивать в самой статье):
0) Что такое палиндром
1) Алгоритм Манакера: Вики, Codeforces, e-maxx
2) Немного про хеши и их применение: e-maxx, Habrahabr
3) Обсуждение про завал хешей на Codeforces: тыц
4) Строки (слова) Туэ-Морса: раз, два
5) Статьи про дерево палиндромов: хорошее описание, codeforces
6) Вот ещё цикл статей про поиск чисел-палиндромов: Хабр