Сайты на кольце
ДНК митохондрии человека и фага φX174 замкнута в кольцо. Записать кольцо в файл можно, только разрезав его где-то: базы данных договорились, с какой буквы начинать, и пишут геном от неё до конца, а последняя буква файла на самом деле соседствует с первой. Фаг лямбда — линейная молекула, но в клетке он замыкается в такое же кольцо своими липкими концами.
Биолог хочет знать, сколько раз каждый мотив встречается на кольце. Вхождение — это позиция, начиная с которой m букв подряд, если идти по кольцу, читаются как мотив. Вхождения могут перекрываться: в кольце AAAA мотив AA встречается четыре раза. Вхождение может проходить через место разреза: начинаться в конце файла и продолжаться с его начала.
Один из тестов — геном митохондрии человека (NC_012920.1), другие — фаги φX174 и лямбда.
Вход
В первой строке — кольцо: строка s из букв A, C, G, T и N длиной n (1 ≤ n ≤ 100 000), как она записана в файле. Во второй — число мотивов q (1 ≤ q ≤ 10). Дальше q строк, в каждой мотив из тех же букв длиной m, 1 ≤ m ≤ n. Суммарная длина мотивов не больше 100 000.
Выход
q строк: для каждого мотива — число позиций кольца, с которых он начинается.
Примеры
Пример 1
GAATTCAGG 3 GAATTC GGGAA A
1 1 3
Пример 2
AAAA 2 AA AAA
4 4
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Вхождение, которое проходит через место разреза, начинается в одной из последних m − 1 букв файла. Что нужно дописать к строке, чтобы такие вхождения стали обычными?
2Подсказка 2
Допишите к s её первые m − 1 букв. Каждое начало 0 … n − 1 получит свои m букв подряд, а лишних начал не появится: позиции ≥ n в новой строке не дают полного вхождения, у них не хватает букв. Осталось посчитать все вхождения, включая перекрывающиеся.
3Подсказка 3
В кольце AAAA сколько раз встречается AA? А что ответит "AAAAA".count("AA")?
4Идея
Кольцо раскладывается в строку t = s + s[0..m − 2] длины n + m − 1. Начала вхождений в t — это ровно позиции 0 … n − 1, и каждая соответствует одной позиции кольца. В t ищем все вхождения поиском КМП: после каждого найденного k становится π[m − 1], поэтому перекрывающиеся вхождения не теряются.
5Разбор
Для каждого мотива строим префикс-функцию, проходим по t и считаем, сколько раз k дошло до m. Склеивать t не обязательно: можно пройти по s и потом ещё раз по её первым m − 1 буквам, не сбрасывая k, — поиск КМП читает текст потоком.
Отдельно стоит случай m = n. Мотив длиной во всё кольцо встречается столько раз, сколько у кольца поворотов, которые читаются как мотив: у ACGACGACG мотив GACGACGAC встречается трижды, потому что кольцо переходит в себя при повороте на три буквы. Решение с дописыванием m − 1 букв учитывает это само.
5+Решение
6Сложность
На мотив — O(n + m): префикс-функция за O(m) и поиск по n + m − 1 буквам. Всего O(q · n + Σm), около миллиона шагов в худшем тесте. Наивный поиск на кольце из одних A и мотиве из 50 000 букв A сделал бы 5·10⁹ сравнений.
7Типичные ошибки
- Поиск без дописывания. Теряются вхождения через место разреза: в кольце AAAA линейный поиск находит AA трижды, а не четыре раза, мотив длины n — один раз, даже если кольцо симметрично.
- Дописать всю строку, а не m − 1 букв. В s + s вхождения, целиком лежащие во второй копии, посчитаются дважды.
str.countиstrings.Count. Обе функции считают вхождения без перекрытий: найдя вхождение, продолжают искать после его конца. В теломере TTAGGG… мотив из двух звеньев они находят вдвое реже, чем он встречается.