STR Строки и тексты Алгоритм
Алгоритм Манакера
Также: Manacher's algorithm · Манакер · самый длинный палиндром · longest palindromic substring · все палиндромы строки · палиндромы в ДНК · обратно-комплементарный палиндром
Все палиндромы строки за один проход: для каждой буквы и каждого промежутка — длина самого длинного палиндрома с центром там. Самый правый найденный палиндром работает как зеркало: радиус в центре внутри него уже известен из отражённого центра.
В ДНК фага λ 48 502 буквы. Слов из шести букв, которые совпадают со своей обратной комплементарной копией, как GAATTC, в ней 460, а по частотам её же коротких слов их ожидалось бы 698. Фаги таких слов избегают: бактерии защищаются ферментами рестрикции, многие из которых режут ДНК как раз по палиндромам, и фагу выгодно, чтобы мест для разреза было меньше. У кишечной палочки избегание слабее, у митохондрии человека его нет вовсе: 212 найденных против 201 ожидаемого. Все палиндромы генома — каждой длины и где каждый — находятся за один проход алгоритмом Манакера.
Самые длинные палиндромы у λ — по 14 букв: TCTGCCGCGGCAGA с позиции 20 526 и GGTTGATATCAACC с позиции 41 269, у митохондрии — TTCGCTTCGAAGCGAA, 16 букв. Такие длинные попадаются редко, а вот слов в шесть букв — сотни, и каждое — возможный разрез. Про то, как фермент EcoRI режет λ по GAATTC, рассказано в главе курса о поиске подстрок; здесь — как найти сразу все палиндромы.
Идея
Центр палиндрома — буква (палиндром нечётной длины) или промежуток между буквами (чётной). Радиус центра — на сколько шагов от него строка остаётся палиндромом. Наивно радиус ищут, расширяясь от каждого центра заново. На тексте это быстро: палиндромы в нём короткие. Но на строке «аааа…а» каждый центр доходит до края, и работы становится порядка n²/4.
Манакер замечает, что палиндром — зеркало. Пусть найден палиндром, который заходит правее всех, — отрезок [l, r] с центром c. Для центра i внутри него отражение j = l + r − i лежит левее, и его радиус уже известен. Всё, что видно вокруг j в пределах отрезка, отражено вокруг i.
Радиус в центре i внутри самого правого палиндрома [l, r] не меньше min(радиус(j), r − i), где j — отражение i. Начинаем с этого числа и сравниваем дальше. Каждое удачное сравнение отодвигает правую границу r, неудачное бывает одно на центр, поэтому всего сравнений O(n).
Чтобы не держать два случая, между буквами вставляют разделитель: «аба» превращается в «|а|б|а|», и у каждого палиндрома появляется центр-позиция. Радиус в новой строке равен длине палиндрома в старой. Посмотрите на зеркало по шагам. Внизу под каждым центром растёт столбик его радиуса, а счётчик сравнивает число сравнений с наивным расширением.
«А роза упала на лапу Азора» — палиндром, который Мальвина диктует Буратино, его приписывают Афанасию Фету. Правая половина целиком лежит внутри палиндрома с центром посередине, и почти каждый её радиус берётся из зеркала без единого удачного сравнения. Самые длинные палиндромы «Войны и мира», если не смотреть на пробелы, знаки и регистр, — по 11 букв, и один из них в бреду раненого князя Андрея: «и пити-пити-пити».
Почему это верно и быстро
Пусть [l, r] — палиндром с центром c, центр i лежит в [c, r], j = l + r − i, а dj — радиус в j. Тогда радиус в i не меньше min(dj, r − i). Если dj < r − i, он равен dj; если [l, r] нельзя расширить и dj > r − i, он равен r − i.
Отражение относительно c переводит позицию x в l + r − x и внутри [l, r] не меняет букв: это палиндром. Пусть k ≤ min(dj, r − i). Позиции i − k и i + k лежат в [l, r] и отражаются в j + k и j − k, где буквы равны, потому что k ≤ dj. Значит, равны и буквы в i ± k.
Если dj < r − i, то на шаге dj + 1 вокруг j буквы разные, и обе позиции ещё внутри [l, r] — их отражения вокруг i тоже разные. Если dj > r − i, обозначим k = r − i + 1. Буква в i − k лежит в отрезке и отражается в j + k, а там, раз k ≤ dj, стоит то же, что в j − k = l − 1. Если бы в i + k = r + 1 была та же буква, что в i − k, то буквы в l − 1 и r + 1 совпали бы и [l, r] расширился бы.
Алгоритм Манакера делает меньше 2m сравнений, где m — длина строки с разделителями.
Неудачное сравнение заканчивает работу с центром — их не больше m. Если начальный радиус меньше r − i, то по теореме о зеркале он окончательный, и первое же сравнение неудачно. Иначе начальный радиус равен r − i (или центр правее r, и он равен нулю), и каждое удачное сравнение открывает позицию правее r. После центра граница становится i + радиус, то есть каждое удачное сравнение сдвигает её ровно на одну позицию. Граница не уходит дальше конца строки, поэтому удачных сравнений меньше m.
Для ДНК всё то же, только «равны» значит «комплементарны»: A напротив T, C напротив G. Отражение внутри обратно-комплементарного палиндрома переводит слово в его обратную комплементарную копию, а у палиндрома она — он сам, поэтому зеркало работает. Центров-букв нет: средняя буква должна была бы быть парой самой себе, а такой буквы в ДНК нет. Остаются промежутки — их радиус и считается в коде, без разделителей.
Код
Для каждого промежутка — радиус обратно-комплементарного палиндрома вокруг него. Палиндромов длины m ровно столько, сколько промежутков с радиусом не меньше m/2: у каждого такого промежутка одно слово длины m. Ожидание — по словам на одну и две буквы короче, как у Гельфанда и Кунина: слово w = a…b встречалось бы N(a…) · N(…b) / N(…) раз, если бы каждая буква зависела только от m − 2 предыдущих.
Сколько это стоит
| Способ | Время | Замечания |
|---|---|---|
| Проверить каждую подстроку | O(n³) | подстрок n²/2, проверка каждой — до n |
| Расширяться от каждого центра | O(n + сумма радиусов) | на тексте почти линейно, на «аааа…» — n²/4 |
| Хеши и двоичный поиск радиуса | O(n log n) | ошибка с малой вероятностью |
| Манакер | O(n) | точно, меньше 2m сравнений |
На геномах наивное расширение почти не проигрывает: палиндромы в них короткие. Но строка из повторов AT — сама себе обратная комплементарная копия, и вокруг каждого второго промежутка палиндром тянется до края. Такие участки, микросателлиты, в настоящих геномах есть.
На четырёх тысячах букв наивный способ медленнее в несколько сотен раз на Python, на 32 тысячах букв на Go — почти в тысячу раз. Манакер растёт линейно и на миллионе букв в Go укладывается в 12 миллисекунд.
Где легко ошибиться
- Только нечётные палиндромы. Если центры — одни буквы, «abba» не найдётся. Нужны и промежутки: два массива радиусов или разделители.
- Разделитель из текста. Если разделитель встречается в строке, он сравнится сам с собой там, где не должен. Берут символ, которого в тексте заведомо нет, или вовсе обходятся двумя массивами.
- Граница включительно или нет. Отражение j = l + r − i выведено для отрезка [l, r] с обоими концами. В листинге палиндром — полуоткрытый кусок букв [left, right), а центры — промежутки, и формула та же только потому, что промежутки нумеруются иначе, чем буквы. Перепутанная формула даёт радиус чужого центра, и ошибка видна не на каждом тесте.
- Нечётные центры в ДНК. С заменой «равно» на «комплементарно» центр-буква не сравнивается ни с чем и тихо принимается — получаются палиндромы, которых нет. В ДНК центры — только промежутки.
- N в последовательности. В митохондрии человека на позиции 3107 стоит N — неизвестная буква. Она не пара ни одной букве и обрывает палиндром, а словарь пар без неё не должен падать.
Где работает
Самый длинный палиндром и все палиндромы строки; число палиндромных подстрок — сумма радиусов. В биоинформатике — обратно-комплементарные палиндромы: участки узнавания ферментов рестрикции, а с допуском на петлю и ошибки — шпильки РНК, но для них нужны уже другие алгоритмы. В олимпиадах Манакер идёт рядом с хешами и деревом палиндромов — структурой Михаила Рубинчика и Арсения Шура 2015 года, которая хранит все различные палиндромы строки.
История
Гленн Манакер опубликовал алгоритм в 1975 году в журнале ACM под названием «Новый линейный онлайн-алгоритм для поиска самого короткого палиндрома в начале строки»: он искал палиндромы в начале строки по мере чтения букв. В 1995 году Альберто Апостолико, Дани Бреслауэр и Цви Галил, строя параллельный алгоритм поиска всех палиндромов, отметили, что тот же приём даёт все максимальные палиндромы строки за линейное время, — так его и используют сейчас. Избегание коротких палиндромов в геномах бактерий описали Михаил Гельфанд и Евгений Кунин в 1997 году: слова длины 4–6 встречаются в них заметно реже ожидаемого, сильнее всего — участки узнавания ферментов рестрикции самого вида, а в геномах митохондрий и хлоропластов избегания нет.
Задачи
Обратно-комплементарные палиндромы генома: самый длинный и сколько их всего. И самый длинный палиндром текста, если не смотреть на пробелы, знаки и регистр, — с выводом куска так, как он стоит в тексте.
Палиндромы в ДНК Палиндром из буквДанные: Геномы: NCBI RefSeq — NC_001416.1 (фаг λ), NC_001604.1 (фаг T7), NC_001422.1 (фаг φX174), NC_000913.3 (кишечная палочка K-12), NC_012920.1 (митохондрия человека); модель ожидания — Гельфанд и Кунин, Nucleic Acids Research, 1997