Палиндром. какие бывают палиндромы?

Примеры палиндромов

Магический квадрат с фразой SATOR AREPO TENET OPERA ROTAS (с лат. — «Сеятель Арепо с трудом держит колеса»), читаемой во всех направлениях

Русский язык:

  • Лёша на полке клопа нашёл (авторство спорно)
  • А роза упала на лапу Азора. (Афанасий Фет)
  • Аргентина манит негра (авторство спорно)
  • Я иду съ мечемъ судия (Гавриил Державин)
  • Я — арка края (Валерий Брюсов)
  • О, лета тело! (Валерий Брюсов)
  • Молебен о коне белом (Илья Фоняков)
  • Лег на храм, и дивен и невидим архангел (фольклор)
  • Искать такси (авторство спорно)

Более сложным видом палиндрома (словесного, а не буквенного) является стихотворение по этому принципу, например:

Результатом опытов поэта-модерниста Велимира Хлебникова с палиндромической поэзией стало его стихотворение «Перевертень»:

Английский язык:

  • «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. Похожие рекорды, но в других «весовых категориях» были установлены Джеральдом Бернсом (англ. Gerald M. Berns, бессмысленный список из 31 358 слов) и Лоуренсом Левиным (англ. Lawrence Levine, связный роман Olson in Oslo из 31 594 слов, написанный с применением странных грамматических структур и архаичного языка и потому трудный для чтения).

Латинский язык:

  • Sum summus mus (Я — сильнейшая мышь)
  • Палиндромическое двустишие, приписываемое самому дьяволу (т.к. в переводе означает «Крестись, Рим, крестись, того не зная, ты затрагиваешь меня и давишь и своими жестами вдруг призываешь к себе  любовь»):

Финский язык:

Saippuakivikauppias (Торговец щёлоком; самое длинное в мире слово-палиндром)

Греческий язык:

Νίψον ανομήματα μη μόναν όψιν (англ.)русск. (Смой грехи, не только лицо).

Казахский язык:

Қазақ (Казах), Ана (Мама), Нан (хлеб), Кек (Месть).

Lychrel процесс

Непалиндромные числа можно соединить с палиндромными числами с помощью ряда операций. Во-первых, непалиндромное число меняется на противоположное, и результат прибавляется к исходному числу. Если результатом не является палиндромное число, это повторяется до тех пор, пока не будет получено палиндромное число. Такой номер называется «отложенным палиндромом».

Неизвестно, могут ли все непалиндромные числа таким образом сочетаться с палиндромными числами. Хотя не было доказано, что ни одно число является непарным, многие, похоже, таковым не являются. Например, 196 не дает палиндрома даже после 700000000 итераций. Любое число, которое никогда не становится палиндромным таким образом, известно как число Ликрела .

24 января 2017 года номер 1 999 291 987 030 606 810 был опубликован в OEIS как A281509 и объявлен «Крупнейшим известным палиндромом с наиболее задержкой». Последовательность 125 261-шаговых палиндромов с наибольшей задержкой, предшествующих 1999 291 987 030 606 810 и не описанных ранее, была опубликована отдельно как A281508 .

Примеры палиндромов

Магический квадрат с фразой SATOR AREPO TENET OPERA ROTAS (с лат. — «Сеятель Арепо с трудом держит колеса»), читаемой во всех направлениях

Русский язык:

  • Лёша на полке клопа нашёл (авторство спорно)
  • А роза упала на лапу Азора. (Афанасий Фет)
  • Аргентина манит негра (авторство спорно)
  • Я иду съ мечемъ судия (Гавриил Державин)
  • Я — арка края (Валерий Брюсов)
  • О, лета тело! (Валерий Брюсов)
  • Молебен о коне белом (Илья Фоняков)
  • Лег на храм, и дивен и невидим архангел (фольклор)
  • Искать такси (авторство спорно)

Более сложным видом палиндрома (словесного, а не буквенного) является стихотворение по этому принципу, например:

Результатом опытов поэта-модерниста Велимира Хлебникова с палиндромической поэзией стало его стихотворение «Перевертень»:

Английский язык:

  • «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. Похожие рекорды, но в других «весовых категориях» были установлены Джеральдом Бернсом (англ. Gerald M. Berns, бессмысленный список из 31 358 слов) и Лоуренсом Левиным (англ. Lawrence Levine, связный роман Olson in Oslo из 31 594 слов, написанный с применением странных грамматических структур и архаичного языка и потому трудный для чтения).

Латинский язык:

  • Sum summus mus (Я — сильнейшая мышь)
  • Палиндромическое двустишие, приписываемое самому дьяволу (т.к. в переводе означает «Крестись, Рим, крестись, того не зная, ты затрагиваешь меня и давишь и своими жестами вдруг призываешь к себе  любовь»):

Финский язык:

Saippuakivikauppias (Торговец щёлоком; самое длинное в мире слово-палиндром)

Греческий язык:

Νίψον ανομήματα μη μόναν όψιν (англ.)русск. (Смой грехи, не только лицо).

Казахский язык:

Қазақ (Казах), Ана (Мама), Нан (хлеб), Кек (Месть).

В биологии


Палиндромы в ДНК: 1 — палиндром; 2 — кольцо; 3 — стебель

В молекулах ДНК присутствует от 100 тыс. до 1 млн коротких палиндромных последовательностей. Принцип их формирования несколько отличается от того, как это происходит для слов и предложений. Поскольку молекула ДНК состоит из двух комплементарных цепочек нуклеотидов, а нуклеотиды всегда соединяются одним и тем же образом (аденин (А) с тимином (Т), цитозин (С) с гуанином (G)), считается, что одноцепочечная последовательность ДНК является палиндромом, если она равна своей комплементарной последовательности, прочитанной задом наперёд. Например, последовательность ACCTAGGT является палиндромной, так как комплементарной ей будет последовательность TGGATCCA, которая совпадает с исходной, прочитанной задом наперёд.

Палиндромные участки распределены по ДНК неравномерно. Они играют важную роль в формировании некоторых типов нуклеиновых кислот, например, в случае транспортных РНК.

Палиндромы в молекулярной генетике

Палиндромные последовательности (A) в двойной цепи могут образовывать пары оснований с аналогичными в одной цепи, чтобы сформировать основу (C) петли (B) шпилечных структур (здесь ДНК)

В молекулярной генетике короткие сегменты ДНК в двойных цепях называют палиндромами, если две цепочки имеют одинаковую последовательность в противоположных направлениях. Такие сегменты ДНК часто служат в качестве последовательности распознавания для рестрикционных ферментов . Ферменты прикрепляются к соответствующему участку и характерным образом разрезают двойную цепь ДНК.

Пример: последовательность распознавания фермента EcoRI

Последовательность распознавания Срезание ограничения
5'-GAATTC-3'
3'-CTTAAG-5'
5'-G       AATTC-3'
3'-CTTAA       G-5'

Рестрикционные ферменты — чрезвычайно важный инструмент молекулярной генетики. Поскольку последовательность распознавания характерна для каждого фермента, ее можно использовать для целенаправленного разрезания молекул ДНК. Поскольку кусок длиной в несколько оснований выступает из одной из двух цепей на границе раздела (см. Липкие концы ), фрагменты ДНК также могут быть снова собраны вместе одинаково целенаправленно.

Последовательности в нуклеотидной последовательности в одной цепи ДНК или РНК также называются палиндромными последовательностями, если две области одной и той же молекулы соответствуют таким образом, что одна последовательность, читаемая в противоположном направлении, совпадает с другой последовательностью. Внутримолекулярные пары оснований между этими областями приводят к двухцепочечным соединениям, которые вместе с образующейся петлей цепи также называются структурами шпильки .

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

Палиндром в эзотерики

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

  • если до этого вас одолевала лень, безразличие и апатия, то после 12 февраля все изменится;
  • прежде всего нужно загадывать желания, мечтать, визуализировать и детализировать. Представьте себе, что все, о чем желаете — уже сбылось. Погружайтесь в свою мечту так, будто уже держите в руках свою «птицу счастья»;
  • нужно обязательно простить своих обидчиков, отпустить все, что грызет вашу душу, освободить голову от негативных мыслей;
  • нумерологи советуют отпустить из жизни все и всех, что доставляет вам негатив и хлопоты. В этот день нужно также попрощаться с людьми, которые вытягивают из вас жизненную энергию;
  • нельзя ни в коем случае завидовать, ругаться и соперничать. Не ставьте себя выше других, не демонстрируйте свое превосходство. 

Разновидности

Теоретики и практики палиндрома выделили многочисленные пограничные с палиндромом формы: например, оборотень — текст, читающийся слева направо иначе, чем справа налево: «Мир удобен» (Сергей Федин). Среди более редких разновидностей палиндромических текстов следует назвать также слоговые, словесные и фразовые палиндромы, двуязычные палиндромы (в одну сторону текст читается на одном языке, в обратную — на другом) и т. п.

Существуют разновидности, когда чтение производится не в обратном направлении, а в прямом, но с другого места в «размноженном» термине, например, кабанкабан, кольцокольцо, викивики.

Примеры палиндромов[ | код]

Магический квадрат с фразой SATOR AREPO TENET OPERA ROTAS (с лат. — «Сеятель Арепо с трудом держит колеса»), читаемой во всех направлениях

Русский язык:

  • Лёша на полке клопа нашёл (авторство спорно)
  • А роза упала на лапу Азора. (Афанасий Фет)
  • Аргентина манит негра (авторство спорно)
  • Я иду съ мечемъ судия (Гавриил Державин)
  • Я — арка края (Валерий Брюсов)
  • О, лета тело! (Валерий Брюсов)
  • Молебен о коне белом (Илья Фоняков)
  • Лег на храм, и дивен и невидим архангел (фольклор)
  • Искать такси (авторство спорно)

Более сложным видом палиндрома (словесного, а не буквенного) является стихотворение по этому принципу, например:

Результатом опытов поэта-модерниста Велимира Хлебникова с палиндромической поэзией стало его стихотворение «Перевертень»:

Английский язык:

  • «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. Похожие рекорды, но в других «весовых категориях» были установлены Джеральдом Бернсом (англ. Gerald M. Berns, бессмысленный список из 31 358 слов) и Лоуренсом Левиным (англ. Lawrence Levine, связный роман Olson in Oslo из 31 594 слов, написанный с применением странных грамматических структур и архаичного языка и потому трудный для чтения).

Латинский язык:

  • Sum summus mus (Я — сильнейшая мышь)
  • Палиндромическое двустишие, приписываемое самому дьяволу (т.к. в переводе означает «Крестись, Рим, крестись, того не зная, ты затрагиваешь меня и давишь и своими жестами вдруг призываешь к себе  любовь»):

Финский язык:

Saippuakivikauppias (Торговец щёлоком; самое длинное в мире слово-палиндром)

Греческий язык:

Νίψον ανομήματα μη μόναν όψιν (англ.)русск. (Смой грехи, не только лицо).

Казахский язык:

Қазақ (Казах), Ана (Мама), Нан (хлеб), Кек (Месть).

Применения[править]

Число новых палиндромов, порождаемых очередным символомправить

Задача:
Необходимо определить число подпалиндромов, которые будут новыми после добавления символа в конец строки .

Например, при добавлении символа к строке , которая уже состоит из палиндромов , и , добавляется новый палиндром .

Мы знаем, что число новых подпалиндромов при добавлении символа или . Так что решение задачи довольно простое — будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).

Также данную структуру можно использовать для подсчета числа различных подпалиндромов строки. Это будет просто число вершин.

Число подпалиндромовправить

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

Например, строка имеет четыре подпалиндрома: дважды , и .

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

Рассмотрим очередной шаг алгоритма после добавления символа . Обозначим за вершину, соответствующую максимальному палиндрому-суффиксу, содержащую этот последний символ.
Заметим, что новые палиндромы, которые добавляет — это , а также все палиндромы, достижимые из по суффиксным ссылкам (т.к. только они содержат новый символ ). Для того чтобы быстро найти их число, будем хранить в каждой вершине длину цепочки суффиксных ссылок до корня (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого очередного по мере добавления новых символов.

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

Число вхождений каждого подпалиндрома в строкуправить

Задача:
Необходимо найти число вхождений каждого подпалиндрома строки в неё саму.

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

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

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

Поиск рефрен-палиндромаправить

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

Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, а затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.

История

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

В Площадь Сатор.

Палиндром был найден как граффито в Геркуланум, город, погребенный пеплом в 79 г. н.э. Этот палиндром, названный Площадь Сатор, состоит из предложения, написанного на латыни: «Сатор Арепо Тенет Опера Ротас«(« Сеятель Арепо с усилием держит колеса »). Примечателен тем, что первые буквы каждого слова образуют первое слово, вторые буквы образуют второе слово и т. Д. Следовательно, это можно расположить в слово квадрат который читается четырьмя разными способами: по горизонтали или вертикали либо сверху слева направо, либо снизу справа, либо сверху слева. Таким образом, их можно назвать палиндроматическими.[нужна цитата]

Палиндром с таким же квадратным свойством — это иврит палиндром, «Мы объяснили, что обжора, которая в меде, была сожжена и сожжена», (רשנו רעבתן שבדבש נתבער ונשרף; перашну: раавтан шебадваш нитбаер венисраф), зачисленные на Авраам ибн Эзра в 1924 г., и ссылаясь на галахический вопрос, делает ли муха, приземляющаяся в мед, мед Treif (некошерный).

Палиндром на шрифте на St Martin, Ludgate

Палиндромная латинская загадка «In girum imus nocte et consumimur igni«(« мы ходим по кругу ночью и пожираем огонь ») описывает поведение мотыльков. Вероятно, этот палиндром скорее из средневековья, чем из древних времен. Второе слово, заимствованное из греческого языка, следует правильно писать извилина.

Византийские греки часто писал палиндром: «Смой грехи, не только лицо» ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ («Nip͜son anomēmata mē monan op͜sin«), приписываемые Григорий Назианзин, на крестильные купели; особенно в базилике Собор Святой Софии в Константинополь. Вариант, также палиндром, заменяет множественное число ΑΝΟΜΗΜΑΤΑ («грехи») в единственном числе ΑΝΟΜΗΜΑ («грех»). Эта практика была продолжена во многих церквях Западной Европы, например, купель в Церковь Святой Марии, Ноттингем а также купель Святого Стефана д’Эгре, Париж; в аббатстве Святого Менина, Орлеан; в Колледж Далвич; и в следующих церквях в Англии: Worlingworth (Саффолк), Харлоу (Эссекс), Knapton (Норфолк), St Martin, Ludgate (Лондон) и Хэдли (Саффолк).

Греческий поэт 1802 года в Вене даже написал стихотворение Ποίημα Καρκινικόν (Карциновая поэма), в Древнегреческий, где каждая из 455 строк была палиндромом.

В английском есть десятки палиндромов слова, Такие как глаз, Госпожа, и обожествленный, но английские писатели обычно цитировали латинские и греческие палиндромные предложения только в начале 19 века, хотя Джон Тейлор придумал одно в 1614 году: «Непотребно жил я и жил злом» (с амперсанд быть чем-то вроде «выдумки»). Обычно это считается первым предложением о палиндроме на английском языке, и оно давно пользуется репутацией (особенно Джеймс «Гермес» Харрис) быть Только один, несмотря на многие попытки найти другие. (Тейлор также сочинил две другие, «довольно безразличные», палиндромные стихотворные строки: «Олень, мадам, Рид», «Считай, если я пойду».) Затем в 1848 году некий «J.T.R.» придумал «Способен был я до того, как увидел Эльбу», который стал известен после того, как его (неправдоподобно) приписали Наполеон.

В недавней истории были соревнования, связанные с палиндромами, такие как Чемпионат мира по палиндромам 2012 года, проходивший в Бруклине, США.

Знаменитые палиндромы

Некоторые хорошо известные английские палиндромы: «Я был способен, прежде чем увидел Эльба» (1848), «Человек, план, канал — Панама» (1948), «Мадам, я Адам» (1861), и «Никогда не четно и нечетно».

Английские палиндромы значительной длины включают математических Питер Хилтон»Док, примечание: я не согласен. Пост никогда не предотвращает ожирения. Я сижу на треске» и шотландский поэт Аластер Рид«Т. Элиот, главный бард, отмечает исходящий гнилостный запах, грустит; я бы дал ему название: комариная грязь на унитазе с тусклым горшком».

Число палиндромов

Палиндромы чисел дают то же значение, если смотреть спереди, что и сзади (например, 151). Сюда также входят простые числа (см. Палиндром простых чисел ). Простые числа, которые при обратном чтении дают не одно и то же значение, а другое простое число, называются mirp-числами .

Дата палиндром

Финиковые палиндромы очень похожи на числовые палиндромы, например Например, 20.02.2002 или 02.02.2020, и временные палиндромы, например Б. 13:31.

2 февраля 2020 года стал всемирным палиндромным днем. Календарная дата может быть с обеих сторон в соответствии с европейской нотации (02/02/2020), в Восточной Азии или ISO нотация (2020.02.02 или 2020-02-02), а также США обозначение (02/02/2020 ) для чтения. Последний раз это было 11.11.1111. Следующие два глобальных палиндромных дня — 12 декабря 2121 года и 3 марта 30:30.

Алгоритм Манакера

Пусть есть строка \(s\) и мы хотим найти в ней все подпалиндромы.

Мы сразу сталкиваемся с очевидной трудностью: их в строке может быть \(O(n^2)\), что можно видеть на примере строки \(s = aa \ldots a\). Поэтому будем использовать следующий формат: для каждой позиции \(s_i\) найдём наибольший палиндром, центр которого совпадает с \(s_i\) (чётные и нечётные палиндромы будем рассматривать отдельно). Половину его длины, округлённую вниз, будем называть радиусом.

Наивное решение — перебрать \(s_i\), а для него вторым циклом находить наибольшую искомую длину:

Тот же пример \(s = aa\dots a\) показывает, что данная реализация работает за \(O(n^2)\).

Для оптимизации применим идею, знакомую из алгоритма z-функции: при инициализации \(t_i\) будем пользоваться уже посчитанными \(t\). А именно, будем поддерживать \((l, r)\) — интервал, соответствующий самому правому из найденных подпалиндромов. Тогда мы можем сказать, что часть наибольшего палиндрома с центром в \(s_i\), которая лежит внутри \(s_{l:r}\), имеет радиус хотя бы \(\min(r-i, \; t_{l+r-i})\). Первая величина равна длине, дальше которой произошел бы выход за пределы \(s_{l:r}\), а вторая — значению радиуса в позиции, зеркальной относительно центра палиндрома \(s_{l:r}\).

Так же, как и z-функция, алгоритм работает за линейное время: цикл запускается только когда \(t_i = r — i\) (иначе палиндром уже во что-то упёрся), и каждая его итерация сдвигает увеличивает \(r\) на единицу. Так как \(r \leq n\), получаем, что суммарно эти циклы сделают \(O(n)\) итераций.

Для случая чётных палиндромов меняется только индексация:

Также можно было не писать отдельно две реализации, а воспользоваться следующим трюком — сделать замену:

\

Теперь нечётные палиндромы с центром в \(s_i\) соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в \(\#\) — чётным.

Небольшое отступление

Вообще, вы когда-нибудь задумывались откуда берётся качественное различие во времени работы алгоритмов? Почему вообще всем алгоритмы не работают, скажем, за линейное время? Интуитивно понятно, что время выполнения зависит от сложности (энтропии, количества информации) задачи, которую решает алгоритм. Что из себя представляет эта сложность? Я придумал такую аналогию — вот есть определённый объём воды, который нужно переместить из точки А в точку Б. Вода, как известно, вещество несжимаемое, поэтому её можно только перелить в какую-то ёмкость. Изначально этот объём нам неизвестен, мы можем только прийти с ёмкостью, попробовать перелить в неё всю воду и посмотреть не пролито ли что-то. Можно взять с собой несколько ёмкостей разного объёма, можно даже проливать остатки, если мы решим что полный объём нам не нужен.

В этой аналогии вода — это врождённая «энтропия» задачи, процесс переноса — алгоритм, а ёмкости — ресурсы, которые необходимо затратить на решение. В информатике хорошо известен т.н. «time-space trade-off» (компромисс между временем и памятью), когда большую временную сложность можно «перелить» в память, качественно уменьшив время работы алгоритма. Кроме времени и памяти есть ещё и другие ёмкости, например, вероятность. Ради выигрыша во времени требование «всегда завершаться только с правильным результатом» можно ослабить если позволить компьютеру иногда ошибаться, но при этом контролировать вероятность ошибки. В этом привлекательность алгоритмов Монте-Карло. То есть вместе с ёмкостями «время» и «память» мы взяли с собой «вероятность», в которую можно перелить часть воды из «времени», но общий объём останется прежним. Под «пролитием» ненужной воды я имею в виду ограничение задачи на какой-то частный случай, в котором присутствует некая регулярность входных данных. Например, если рассматривать только целые числа из определённого интервала, то можно сортировать за линейное время. Поиск в отсортированном массиве занимает логарифм времени, а не линию. Обычно на практике хватает именно такого частного случая, да и сами размеры редко превышают какие-то разумные пределы. Другая неочевидная ёмкость — длина исходного кода.

Самое главное, что мы не знаем заранее точный объём воды. Мы можем только измерять его ёмкостями, но редко бывает так, что мы находим ёмкость вровень сложности. В истинном объёме многих задач мы не уверенны до сих пор (P vs. NP). Можно конечно взять с собой целую цистерну (решение «в лоб»), тогда точно ничего не прольётся, но в этой цистерне вполне может плескаться одна лишь кружка.

Вернёмся к нашей задаче.

Описание структуры[править]

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

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

Обозначим корни этих деревьев за и соответственно.

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

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

При реализации в целях экономии памяти мы не будем хранить для каждой вершины соответствующую ей строку-палиндром. Этот подход был бы неэффективным с точки зрения памяти. Вместо этого мы будем хранить только длину палиндрома (и для некоторых задач позицию палиндрома в строке).

Итак, структура будет состоять из двух деревьев и, соответственно, двух корней. Для удобства реализации каждый корень будет соответствовать фиктивной строке.

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

Суффиксные ссылки обоих корней будут вести к вершине . Это соглашение нужно также для удобства реализации — теперь каждая вершина имеет суффиксную ссылку.

В биологии


Палиндромы в ДНК: 1 — палиндром; 2 — кольцо; 3 — стебель

В молекулах ДНК присутствует от 100 тыс. до 1 млн коротких палиндромных последовательностей. Принцип их формирования несколько отличается от того, как это происходит для слов и предложений. Поскольку молекула ДНК состоит из двух комплементарных цепочек нуклеотидов, а нуклеотиды всегда соединяются одним и тем же образом (аденин (А) с тимином (Т), цитозин (С) с гуанином (G)), считается, что одноцепочечная последовательность ДНК является палиндромом, если она равна своей комплементарной последовательности, прочитанной задом наперёд. Например, последовательность ACCTAGGT является палиндромной, так как комплементарной ей будет последовательность TGGATCCA, которая совпадает с исходной, прочитанной задом наперёд.

Палиндромные участки распределены по ДНК неравномерно. Они играют важную роль в формировании некоторых типов нуклеиновых кислот, например, в случае транспортных РНК.