Кольцевой геном
У кольцевой молекулы ДНК нет начала. Геном фага φX174 и митохондрии человека — кольца, геном фага λ замыкается в кольцо, попав в клетку. Две лаборатории прочитали один и тот же кольцевой геном, но начали с разных мест, и во второй записи есть ошибки чтения: некоторые буквы заменены другими. Найдите, на сколько сдвинута вторая запись относительно первой.
Даны строки A и B одной длины n. Для сдвига k (0 ≤ k < n) число совпадений — сколько есть позиций i, где B[i] = A[(i + k) mod n] (позиции с нуля). Выведите сдвиг с наибольшим числом совпадений и само это число; если таких сдвигов несколько — наименьший.
Тесты со второго по пятый — настоящие геномы из базы NCBI RefSeq: фаг φX174 (5386 букв, ошибки в 2% букв), митохондрия человека (16 569 букв, 5%) и дважды фаг λ (48 502 буквы, 10% и 40%).
Вход
Две строки — A и B, одинаковой длины n (1 ≤ n ≤ 50 000), из букв A, C, G, T и N.
Выход
Два числа через пробел: сдвиг k и число совпадений при нём.
Примеры
Пример 1
GATTACAT ACATGATT
4 8
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 4000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебрать все сдвиги и сравнить строки — n² сравнений, для генома фага λ — 2,35 миллиарда. Это слишком много, а ошибки чтения не дают искать точное вхождение строки в строку. Нужно посчитать совпадения для всех сдвигов сразу.
2Подсказка 2
Возьмите одну букву, например G. Запишите строки как последовательности нулей и единиц: единица там, где стоит G. Число совпадений по букве G при сдвиге k — это сумма Σi a[i + k] · b[i]. Где ещё встречаются суммы произведений такого вида для всех k одновременно?
3Подсказка 3
Коэффициенты произведения двух многочленов — это суммы Σ a[i] · b[j] по i + j = const. Переверните одну из строк — и индексы сложатся как надо.
4Идея
Для каждой буквы c возьмём многочлены P(x) = Σ [A[j] = c] xj и Q(x) = Σ [B[n − 1 − i] = c] xi. Коэффициент произведения при xn−1+s равен Σi [A[i + s] = c]·[B[i] = c] — совпадения буквы c при линейном сдвиге s. Сложив произведения для всех букв, получаем совпадения для всех s от −(n − 1) до n − 1, а на кольце сдвиг k — это два линейных: s = k (позиции, где i + k < n) и s = k − n (остальные). Многочлены длины 50 000 перемножаются Карацубой за доли секунды.
5Разбор
Go. Пишем Карацубу на срезах целых: три произведения половин, ниже порога в несколько десятков коэффициентов — столбик. Переносов нет — это многочлены. Значения в рекурсии растут, но не выходят за 32 бита: коэффициенты конечного произведения не больше n, а промежуточные суммы половин — не больше 2глубина.
Python. Писать Карацубу на списках медленно, зато она уже есть внутри целых чисел Python. Упакуем многочлен в одно большое целое: коэффициент j — в биты с 16j по 16j + 15. Так как коэффициенты произведения не больше n ≤ 50 000 < 216, они не перетекают в соседние слоты, и после умножения их можно прочитать обратно: to_bytes и memoryview(…).cast("H"). Это подстановка Кронекера: умножение многочленов сведено к умножению чисел. Для генома фага λ это умножения чисел примерно по 800 тысяч бит — для CPython мгновенно.
Ответ. Для каждого k складываем C[n − 1 + k] и C[k − 1] (при k ≥ 1) и берём максимум с наименьшим k.
5+Решение
6Сложность
Не больше пяти букв, по одному произведению многочленов длины n на букву: O(n1,585) Карацубой. Через быстрое преобразование Фурье — O(n log n); при n = 50 000 хватает и Карацубы.
7Типичные ошибки
- Перебор сдвигов. Верно, но квадратично: на геноме фага λ не укладывается во время.
- Только линейный сдвиг. Если забыть второе слагаемое
C[k − 1], теряются совпадения тех позиций, которые «перешли через конец» кольца, и ответ при больших сдвигах оказывается меньше настоящего. - Тесные слоты. При упаковке в целое ширина слота должна вмещать самый большой коэффициент произведения, а он доходит до n; 8 бит не хватит — коэффициенты перельются в соседей.
- Ничьи. В седьмом тесте строка периодична, и одинаково хороших сдвигов много — нужен наименьший.