Где начинается кольцо
У многих вирусов и бактерий ДНК замкнута в кольцо: у неё нет ни начала, ни конца. Кольцо прочитали дважды. Первое прочтение начинается где-то, второе — совсем в другом месте того же кольца, к тому же прибор во втором прочтении ошибся в некоторых буквах. Нужно понять, с какого места первого прочтения начинается второе.
Формально: даны строки s и t одной длины n из букв A, C, G, T. Для сдвига d (0 ≤ d < n) число совпадений — это количество позиций j, для которых tj = s(j + d) mod n. Найдите сдвиг с наибольшим числом совпадений.
Вход
Две строки: s и t, каждая длины n (1 ≤ n ≤ 2 · 10⁵), из букв A, C, G, T.
Выход
Два числа: сдвиг d с наибольшим числом совпадений и само это число. Если таких сдвигов несколько, выведите наименьший.
Примеры
Пример 1
ACGTTGCAAG CAAGACGTAG
6 9
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сравнить строки при одном сдвиге — n операций, сдвигов n: всего 4 · 10¹⁰. Для фага φX174 из 5386 букв так ещё можно, для фага лямбда из 48 502 — уже нет.
2Подсказка 2
Совпадение букв трудно складывать, а числа — легко. Возьмите одну букву, например A, и замените строку на нули и единицы: 1 там, где стоит A. Что посчитает сумма произведений этих единиц при сдвиге d?
3Идея
Для буквы c положим ai = 1, если si = c, и bj = 1, если tj = c. Тогда Σj bj · a(j + d) mod n — число позиций, где при сдвиге d обе строки показывают букву c. Сумма по четырём буквам — искомое число совпадений. А такая сумма для всех d сразу — круговая взаимная корреляция, и быстрое преобразование Фурье считает её за O(n log n): преобразовать оба массива, умножить первый на сопряжённый второй, преобразовать обратно.
4Разбор
В Python с numpy это несколько строк на букву: irfft(rfft(a) * conj(rfft(b)), n) даёт корреляцию длины ровно n, и никакого дополнения нулями не нужно — numpy умеет преобразования любой длины, а круговая корреляция здесь и нужна: кольцо.
Своё БПФ на Go работает с длинами-степенями двойки, поэтому круг разворачиваем: s записываем дважды подряд, t переворачиваем, и обычная свёртка в индексе d + n − 1 даёт совпадения при сдвиге d. Длина преобразования — степень двойки не меньше 3n. Чтобы не делать по три преобразования на букву, оба массива одной буквы кладём в одно комплексное число: s в действительную часть, t — в мнимую. Мнимая часть квадрата (x + iy)² равна 2xy — это и есть нужное произведение. Квадраты четырёх букв складываем и делаем одно обратное преобразование.
Во втором и третьем тестах — настоящие фаги из базы NCBI: φX174, чья ДНК кольцевая, и лямбда, чья ДНК в клетке замыкается в кольцо липкими концами. Даже при 30 % ошибок в четвёртом тесте правильный сдвиг выделяется: случайные совпадения дают около четверти позиций, а правильный сдвиг — 70 %.
4+Решение
5Сложность
Пять преобразований длины 2²⁰ на Go или двенадцать преобразований длины n на Python: O(n log n). Значения корреляции не больше 2 · 10⁵, и округление после обратного преобразования восстанавливает их точно.
6Типичные ошибки
- Все сдвиги в лоб. Проходит φX174 и падает на лямбде: 48 502² ≈ 2,4 · 10⁹ сравнений.
- Найти начало по первым буквам. Искать в s первые двадцать букв t — быстро, но если в них ошибка прибора, точного совпадения нет вовсе, а при повторах в геноме совпадений несколько.
- Обычная свёртка вместо круговой. Без удвоения s хвост второго прочтения, ушедший за конец первого, не будет сравнён ни с чем.
- Ничьи. Строка ACGTACGT… совпадает сама с собой при сдвигах 0, 4, 8, … — нужен наименьший; пятый тест об этом.