Счёт по перестановке
Геном хранят не текстом, а в виде преобразования Барроуза — Уилера. К тексту T из букв A, C, G, T приписан знак $, который меньше всех букв, все циклические сдвиги T$ отсортированы по алфавиту, и выписаны последние буквы сдвигов сверху вниз. Это строка L — и больше у вас ничего нет.
Для каждого слова из списка посчитайте, сколько раз оно встречается в T. Вхождения могут перекрываться: в AAAA слово AA встречается три раза.
В тестах — геномы фагов λ, HK97, HK022 и φX174, митохондрии человека, миллион случайных букв и куски генома, повторённые много раз; среди слов — места ферментов рестрикции, как в статье.
Вход
В первой строке — L: строка из букв A, C, G, T и одного знака $, длиной от 2 до 106 + 1. Во второй — число слов q (1 ≤ q ≤ 105). Дальше q строк — слова из букв A, C, G, T длиной от 1 до 100; их суммарная длина не больше 4·105.
Выход
q чисел, по одному в строке: сколько раз каждое слово встречается в T.
Примеры
Пример 1
GC$AAAC 6 A AC CA G T ACAACG
3 2 1 1 0 1
Пример 2
T$AAAAA 6 A AA AAA AAAAAA AT TA
5 4 3 0 1 0
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Текст можно восстановить из L за n шагов, а потом искать каждое слово. Но слов до ста тысяч, а текст — миллион букв: проход по тексту для каждого слова — 1011 действий. Нужно что-то, что не зависит от длины текста.
2Подсказка 2
Строки отсортированной таблицы, которые начинаются с одного и того же слова, стоят подряд. Пусть известен отрезок строк, начинающихся с хвоста слова Q. Как по нему и по L найти отрезок строк, начинающихся с cQ?
3Идея
Обратный поиск из статьи. Пусть C[c] — сколько букв L меньше c (в L те же буквы, что в T$), а rankc(i) — сколько раз c встречается в L[0..i). Если строки, начинающиеся с Q, — это [lo, hi), то строки, начинающиеся с cQ, — это [C[c] + rankc(lo), C[c] + rankc(hi)). Начинаем с [0, n) и читаем слово с последней буквы; длина итогового отрезка — ответ. Каждая строка таблицы — циклический сдвиг, но раз $ встречается один раз, строка начинается со слова ровно тогда, когда слово встречается в T с этого места, — перекрывающиеся вхождения тоже считаются.
4Разбор
Для пяти знаков $, A, C, G, T заранее посчитаем rank для всех i от 0 до n — пять массивов по n + 1 числу. Тогда каждый шаг поиска — два обращения к массиву. В Python удобно сделать маску «1, где буква c», методом bytes.translate и накопить её через itertools.accumulate в array: так массивы строятся быстро и занимают по 8 байт на число, а не по 36, как список целых.
В первом примере L = GC$AAAC, текст — ACAACG: A встречается 3 раза, AC — 2, CA — 1, G — 1, T — ни разу, всё слово — 1 раз.
4+Решение
5Сложность
Подготовка — O(n) на каждый из пяти знаков, ответы — O(сумма длин слов). Память — пять массивов по n + 1 числу. Если память дороже времени, счётчики хранят через каждые 64 строки и досчитывают остаток по L, как в статье.
6Типичные ошибки
- Восстановить текст и искать через find. Восстановление правильное и быстрое, но потом каждое слово ищется проходом по миллиону букв — в тесте 7 сто тысяч слов не уложатся во время.
- str.count вместо счёта перекрывающихся.
"AAAAAA".count("AA")— это 3, а вхождений 5. Обратный поиск перекрытия считает сам. - Читать слово с начала. Отрезок продлевается только влево: прибавлять буквы нужно справа налево.
- Пустой отрезок. Когда lo ≥ hi, дальше считать не нужно: ответ 0.