Звено повтора
На концах хромосом человека звено TTAGGG повторяется тысячи раз подряд, в других местах генома повторяются звенья CA, CCCCCTCTA и сотни других. Секвенатор читает ДНК кусками — ридами, и рид из такого повтора почти никогда не начинается с начала звена и не кончается на его конце: GGGTTAGGGTTAGGGTT — это теломера, прочитанная с четвёртой буквы звена и оборванная на второй.
По риду s длины n найдите самое короткое звено: наименьшее p, при котором каждая буква рида повторяет букву, стоящую на p левее, то есть s[i] = s[i + p] для всех 0 ≤ i < n − p. Звеном считается начало рида длины p. Если в риде помещаются хотя бы две полные копии звена (2p ≤ n), рид считается повтором. Для рида без повторов p = n.
Среди тестов — настоящие повторы митохондрии человека и куски генома фага лямбда.
Вход
В первой строке число ридов t (1 ≤ t ≤ 1000). В каждой из следующих t строк — рид из букв A, C, G, T и N. Суммарная длина ридов не больше 300 000.
Выход
Для каждого рида — строка из трёх частей через пробел: длина звена p, само звено (первые p букв рида) и слово repeat, если 2p ≤ n, или no, если нет.
Примеры
Пример 1
3 GGGTTAGGGTTAGGGTT CACACACA ACGT
6 GGGTTA repeat 2 CA repeat 4 ACGT no
Пример 2
2 AAAA ACAACAAC
1 A repeat 3 ACA repeat
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Длина рида не обязана делиться на длину звена. У GGGTTAGGGTTAGGGTT 17 букв, а звено — 6. Проверять только делители n нельзя.
2Подсказка 2
Что значит «каждая буква повторяет ту, что на p левее»? Сравните первые n − p букв рида с последними n − p.
3Подсказка 3
p — период ровно тогда, когда начало длины n − p совпадает с концом той же длины, то есть когда у рида есть грань длины n − p. Самому короткому периоду соответствует самая длинная грань.
4Идея
Наименьший период равен n − π[n − 1], где π — префикс-функция рида. Это теорема из статьи о КМП: условие s[i] = s[i + p] для всех i < n − p дословно означает, что s[0..n − p − 1] = s[p..n − 1].
5Разбор
Для каждого рида считаем префикс-функцию, берём p = n − π[n − 1] и печатаем p, первые p букв и repeat, если 2p ≤ n.
Посмотрите на настоящие повторы митохондрии из третьего теста. Звено CA у позиции 514 повторено пять раз. Звено CCCCCTCTA у позиции 8272 повторено дважды — это тот самый девятибуквенный повтор, одна копия которого у части людей выпала. А серия CCCCCCCTCCCCC у позиции 303 периодом 8 не повтор вовсе: в 13 буквах не помещаются две копии звена CCCCCCCT. Период есть у любой строки, повтором его делает только то, что звено укладывается хотя бы дважды.
5+Решение
6Сложность
Префикс-функция рида длины n — O(n), всего O(Σn) = 300 000 шагов. Проверка всех кандидатов p подряд с полным сравнением стоила бы O(n²) — на риде из 300 000 букв это десятки миллиардов сравнений.
7Типичные ошибки
- Только делители длины. Ищут p, при котором рид — ровно n/p копий звена. Рид, оборванный посреди звена, такой проверки не проходит, и теломера оказывается «без повтора» (первый пример).
- Самая длинная грань вместо периода. π[n − 1] — длина грани, а не звена: у GGGTTAGGGTTAGGGTT грань 11, звено 6.
- Звено «как в справочнике». Звено печатается с первой буквы рида: GGGTTA, а не TTAGGG. Повороты звена — тоже звенья того же повтора, но условие спрашивает именно начало рида.