Кольцо из кусков
Геном фага — кольцо из букв A, C, G и T. Секвенатор прочитал его кусками: для каждой позиции кольца — кусок из k букв, начинающийся в ней (у кольца нет конца, поэтому последние куски переходят через начало). Куски перемешаны, где какой стоял — неизвестно, и одинаковые куски могут встречаться несколько раз. Соберите кольцо.
Если колец, подходящих к кускам, несколько, годится любое. Пятый тест — настоящий фаг φX174 (NCBI RefSeq NC_001422.1, 5386 букв) с k = 12, шестой — митохондрия человека (NC_012920.1, 16 569 букв) с k = 16.
Вход
В первой строке n и k (2 ≤ k ≤ n ≤ 200 000, k ≤ 32) — длина кольца и длина куска. Дальше n строк по k букв — куски в произвольном порядке. Гарантируется, что они получены из какого-то кольца длины n.
Выход
Строку из n букв — кольцо, прочитанное с любого места. Её куски длины k, взятые по кругу, должны в точности совпасть с данными, вместе с повторами.
Примеры
Пример 1
7 3 GAT CAG TTA AGA ACA ATT TAC
GATTACA
Пример 2
10 3 GAC ATG TGC CAT TTG GCA ACA ATT CAT TGA
GACATGCATT
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 3000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Соседние куски кольца перекрываются на k − 1 букву. Попробуйте сделать вершинами графа не сами куски, а их перекрытия.
2Подсказка 2
Если идти от куска к куску, выбирая любое подходящее продолжение, в примере 2 можно вернуться в начало, не использовав все куски. Что делать с оставшимися?
3Идея
Граф де Брёйна: вершины — строки длины k − 1, каждый кусок — ребро от своих первых k − 1 букв к последним. Кольцо — замкнутый путь, проходящий каждое ребро ровно раз, то есть эйлеров цикл. Он существует: в кольце у каждой вершины столько же входящих рёбер, сколько исходящих, и граф связен. Наоборот, любой эйлеров цикл читается как кольцо с теми же кусками. Значит, достаточно найти любой эйлеров цикл — алгоритмом Хирхольцера.
4Разбор
Словарь «вершина → список концов её рёбер» и указатель на следующее непройденное ребро у каждой вершины. Стек: пока у вершины на его верху есть непройденное ребро, идём по нему и кладём конец в стек; иначе выталкиваем вершину в ответ. В ориентированном графе ребро видно только из начала, поэтому отметки «пройдено» не нужны — хватает указателя. Ответ, прочитанный задом наперёд, — последовательность вершин цикла; кольцо — первая вершина и последние буквы всех остальных, без повторного хвоста из k − 1 букв.
Почему не годится простой обход «иди, пока идётся»: во втором примере он может пройти GA → AC → CA → AT → TT → TG и сразу вернуться в GA. Там рёбер больше нет, а куски ATG, TGC, GCA и второй CAT остались непройденными. Хирхольцер в этот момент отступает до TG, у которой ещё есть ребро, и вклеивает пропущенную петлю TG → GC → CA → AT → TG.
Собранное кольцо не обязано совпасть с настоящим геномом. В пятом тесте десять разных строк по 11 букв встречаются в φX174 больше одного раза, и разные эйлеровы циклы дают разные кольца с одними и теми же кусками — поэтому проверка принимает любое из них. С k = 14 кольцо было бы единственным: об этом в статье.
4+Решение
5Сложность
O(n · k): каждое ребро проходится один раз, а строки длины k хешируются и копируются. Память — словарь на n рёбер.
6Типичные ошибки
- Обход без склейки. Застревает при первом же повторе, который замыкает петлю раньше времени; кольцо выходит короче n.
- Куски как вершины. Тогда кольцо — путь через все вершины, гамильтонов, и искать его перебором безнадёжно уже на сотне кусков.
- Повторы выброшены. Одинаковые куски — разные рёбра: если хранить их во множестве, рёбер станет меньше и кольцо укоротится.