Праймер без двойников
Чтобы размножить ген в пробирке методом ПЦР, к нему подбирают праймеры — короткие цепочки ДНК, с которых начинается копирование. Прямой праймер повторяет начало гена. ДНК двухцепочечная, и праймер садится туда, где на одной из нитей стоит последовательность, комплементарная ему. Поэтому он сядет не только на начало гена, но и в любое место, где в гене снова встречается та же последовательность, и туда, где в гене стоит её обратное дополнение: буквы заменены парами A↔T, C↔G и записаны в обратном порядке. Каждое лишнее место — лишние копии в пробирке.
Упростим: праймер — начало гена длины k, и он годится, если эта последовательность встречается в гене ровно один раз, в самом начале, и ни разу не встречается в обратном дополнении гена. Для каждого гена найдите наименьшее такое k. Если не годится ни одно начало, вплоть до всего гена, выведите −1.
Например, у гена ATGTTTCAT обратное дополнение — ATGAAACAT. Начало ATG встречается в нём, поэтому праймер из трёх букв сядет и на другую нить; годится только ATGT, k = 4. Среди тестов — девятнадцать генов фага лямбда и тринадцать белковых генов митохондрии человека.
Вход
В первой строке число генов t (1 ≤ t ≤ 1000). В каждой из следующих t строк — ген из букв A, C, G, T. Суммарная длина генов не больше 300 000.
Выход
Для каждого гена — в отдельной строке наименьшее подходящее k или −1.
Примеры
Пример 1
3 ATGACATGAC ATGCAT ATGTTTCAT
6 -1 4
Пример 2
1 ATGTACTAAGGAGGTTGTATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCTTTGGGCAAACCAAGACAGCTAAAGATCTCGGCGTATATCAAAGCGCGATCAACAAGGCCATTCATGCAGGCCGAAAGATTTTTTTAACTATAAACGCTGATGGAAGCGTTTATGCGGAAGAGGTAAAGCCCTTCCCGAGTAACAAAAAAACAACAGCATAAATAACCCCGCTCTTACACATTCCAGCCCTGAAAAAGGGCATCAAATTAAACCACACCTATGGTGTATGCATTTA
5
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если начало длины k годится, то годится и любое более длинное: у длинного начала двойников не больше, чем у короткого. Значит, ответ — это «самое длинное начало, у которого двойник есть» плюс один.
2Подсказка 2
Самое длинное начало, которое снова встречается в гене с позиции i, — это z[i], значение Z-функции гена. Осталась другая нить.
3Подсказка 3
Встречается ли начало гена в его обратном дополнении — это поиск начала строки g в другой строке. Склейте g + «#» + обратное дополнение и посчитайте Z-функцию склейки.
4Идея
Пусть M — самая длинная длина, на которую начало гена совпадает с текстом в каком-нибудь другом месте: на своей нити это max z[i] по i ≥ 1, на чужой — максимум Z-функции склейки g + «#» + rc(g) по позициям правее «#». Все начала длиной до M имеют двойника, начало длины M + 1 — уже нет. Ответ M + 1, если это не больше длины гена.
5Разбор
Две Z-функции на ген: самого гена и склейки с обратным дополнением. Разделитель «#» не даёт совпадению перешагнуть из гена в дополнение, поэтому значения справа от него — ровно длины общих начал гена и хвостов дополнения.
Ответ −1 бывает только у гена, который сам себе обратное дополнение, как сайт фермента GAATTC: тогда даже весь ген встречается на другой нити. У настоящих генов ответы маленькие, 4–9 букв, и это понятно: случайное слово из k букв встречается в гене длины n примерно n/4k раз. Настоящие праймеры длиннее, 18–25 букв, потому что должны быть единственными во всём геноме, а не в одном гене, и садиться прочно.
5+Решение
6Сложность
O(n) на ген длины n, всего O(Σn) — около 900 тысяч шагов Z-алгоритма на самый большой тест. Перебор k с поиском подстроки каждый раз стоит O(n) на одно k: на гене, где начало повторяется на 20 000 букв, это миллиарды сравнений.
7Типичные ошибки
- Только своя нить. Ищут двойников начала лишь в самом гене. У гена ATGTTTCAT получается 3, хотя ATG стоит в обратном дополнении ATGAAACAT, и праймер сядет туда.
- Дополнение без разворота. Заменить буквы парами мало: другая нить читается в обратную сторону. TACAAAGTA — не та последовательность, на которую сядет праймер.
- z[0] в максимуме. По соглашению z[0] — длина всей строки, и если не исключить его, ответ всегда −1.