Палиндромы в ДНК
ДНК — две нити, и вторая читается как первая задом наперёд с заменой A↔T и C↔G. Кусок, который при такой замене не меняется, называют палиндромом: например, GAATTC — его узнаёт фермент EcoRI. Найдите в последовательности самый длинный палиндром и посчитайте, сколько всего в ней палиндромов: каждое вхождение каждой длины считается отдельно.
Тесты с третьего по шестой — геномы фагов λ, T7 и φX174 и митохондрии человека из NCBI. В митохондрии одна буква N — неизвестный нуклеотид: он не пара ни одной букве.
Вход
Одна строка из букв A, C, G, T и N длиной от 1 до 5 · 10⁵.
Выход
В первой строке — длина самого длинного палиндрома и номер его первой буквы (с единицы); если длинных несколько, — самый левый; если палиндромов нет, — 0 0. Во второй строке — число всех палиндромов.
Примеры
Пример 1
CCGAATTCGTTA
8 2 7
Пример 2
ACGTTAACGT
10 1 9
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Может ли у палиндрома в ДНК быть нечётная длина? Что тогда должно быть со средней буквой?
2Подсказка 2
Центр палиндрома — промежуток между буквами. Если вокруг промежутка палиндром длины 2r, то вокруг него же есть палиндромы длин 2, 4, …, 2r, и других с этим центром нет. Значит, ответ на второй вопрос — сумма радиусов. Осталось найти радиус каждого промежутка быстрее, чем расширяясь заново.
3Идея
Алгоритм Манакера с заменой «равно» на «комплементарно». Отражение внутри палиндрома переводит слово в его обратную комплементарную копию, а у палиндрома она — он сам, поэтому зеркало работает: радиус в промежутке внутри самого правого палиндрома не меньше радиуса в отражённом промежутке, урезанного до границы.
4Разбор
Идём по промежуткам слева направо и храним самый правый палиндром [left, right). Для промежутка i внутри него начинаем с min(радиус(left + right − i), right − i), дальше сравниваем пары букв наружу. Буква N не пара никому — словарь пар без неё просто не находит пары. Сумма радиусов на строке ATAT… длины 5 · 10⁵ — 6,25 · 10¹⁰: нужен 64-битный счётчик.
4+Решение
5Сложность
O(n): удачное сравнение сдвигает правую границу, неудачное — одно на промежуток.
6Типичные ошибки
- Расширяться от каждого центра заново. Это
wrong.py. На геномах он успевает — палиндромы там короткие. Но в седьмом тесте строка ATAT…AT, и вокруг каждого второго промежутка палиндром тянется до края: работы около n²/4. - Нечётные центры. Если искать палиндромы и вокруг букв, сравнивая буквы попарно с заменой, средняя буква ни с чем не сравнится и примется молча: «палиндром» ACG окажется найденным.
- Тридцать два бита. Ответ в седьмом тесте не помещается в int32.
- Не самый левый. При равной длине нужен палиндром, который начинается раньше; обновлять ответ только при строго большей длине.