Суффиксы генома по разрядам
Чтобы быстро находить любой фрагмент в геноме, биологи строят суффиксный массив: выписывают все суффиксы генома — хвосты, начинающиеся с каждой позиции, — и сортируют их по алфавиту. Тогда все вхождения фрагмента оказываются в массиве подряд, и их находит двоичный поиск. Постройте суффиксный массив: выведите начала суффиксов в порядке их возрастания.
Для строки GATTACA суффиксы по алфавиту — A, ACA, ATTACA, CA, GATTACA, TACA, TTACA, и их начала — 6, 4, 1, 5, 0, 3, 2. Закрытые тесты — настоящие геномы из базы NCBI: фаг φX174 (5386 букв), митохондрия человека (16 569) и фаг лямбда (48 502), а ещё строки из одной буквы и с коротким периодом, где соседние суффиксы совпадают на десятки тысяч символов.
Вход
Одна строка длиной от 1 до 50 000 из заглавных букв A, C, G, T.
Выход
Одна строка: n чисел через пробел — позиции начал суффиксов (с нуля) в порядке возрастания суффиксов. Суффикс, который является началом другого, меньше его.
Примеры
Пример 1
GATTACA
6 4 1 5 0 3 2
Пример 2
GAGTTTTATCGCTTCCATGACGCAGAAGTTAACACTTTCGGATATTTCTGATGAGTCGAA
59 58 30 25 31 19 33 23 53 26 1 41 7 16 50 43 32 22 15 14 56 20 9 38 47 11 34 57 24 18 52 0 40 49 21 10 39 54 27 2 29 6 42 13 55 8 37 46 17 51 48 28 5 12 36 45 4 35 44 3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сравнить два суффикса напрямую — значит читать их, пока не встретится различие. У строки AAAA…A соседние суффиксы совпадают почти целиком, и одно сравнение стоит десятки тысяч шагов. Нужно сравнивать не символы, а что-то короче.
2Подсказка 2
Пусть суффиксы уже упорядочены по первым k символам, и каждому присвоен ранг — номер его группы в этом порядке. Как по рангам упорядочить суффиксы по первым 2k символам? Первые 2k символов суффикса i — это его первые k символов и первые k символов суффикса i + k.
3Подсказка 3
Порядок по 2k символам — это порядок пар (ранг i, ранг i + k). Пара из двух чисел меньше n — двузначное число в системе с основанием n, и его сортирует поразрядная сортировка: два прохода подсчётом.
4Идея
Это удвоение префиксов. Начинаем с рангов по первому символу. На каждом шаге суффикс i получает пару (ранг i, ранг i + k); если суффикс короче, второй ранг считаем меньше всех — пустой хвост идёт раньше любого символа. Сортируем пары, раздаём новые ранги (равные пары — равный ранг) и удваиваем k. Когда все ранги различны, порядок окончательный; это случится не позже, чем k дорастёт до n, то есть за ⌈log₂ n⌉ шагов.
5Разбор
Корректность держится на одном наблюдении: строки длины 2k сравниваются как пары своих половин, сначала по первой, при равенстве по второй, — а ранги половин сравниваются так же, как сами половины. Поэтому после шага с длиной k ранги упорядочивают суффиксы по первым 2k символам.
Пары сортируем поразрядно: сначала устойчивой сортировкой подсчётом по второму рангу, потом — тоже устойчиво — по первому. Так устроено решение на Go: два прохода по n + 1 счётчиков на шаг. На Python удобнее сложить пару в одно число r1·(n + 2) + r2 и отсортировать встроенной сортировкой: она написана на C и на 50 тысячах целых чисел быстрее подсчёта на Python, хотя асимптотически это O(n log n) на шаг, а не O(n). Ранги первого шага — номера букв в отсортированном алфавите строки, чтобы они были меньше множителя.
Удвоение описали Уди Манбер и Джин Майерс в 1990 году — в той же работе, где ввели суффиксные массивы. Сейчас есть и линейные алгоритмы построения, но удвоение проще всего написать без ошибок, и на геномах в десятки тысяч букв его хватает с запасом.
5+Решение
6Сложность
Шагов не больше ⌈log₂ n⌉ + 1, каждый с поразрядной сортировкой пар — O(n), всего O(n log n); со встроенной сортировкой на шаге — O(n log² n). На случайных строках и настоящих геномах ранги различаются уже через несколько шагов: длинные повторы в них редки. Худший случай — строка из одной буквы, ей нужны все шаги. Память — несколько массивов длины n.
7Типичные ошибки
- Сортировать сами суффиксы. Ключ
s[i:]копирует хвост строки, и все ключи вместе занимают n²/2 символов: на геноме фага лямбда это больше гигабайта. Решение упирается в память. - Множитель меньше рангов. Если склеивать пару в число r1·M + r2, множитель M должен быть больше любого второго ранга. Коды букв (до 84 у
T) больше длины коротких строк — поэтому первые ранги берут по алфавиту строки, а не по кодам. - Пустой хвост как самый большой. Суффикс, которому не хватило символов, должен идти раньше, а не позже:
AменьшеAC.
Алгоритмы задачи
O(n + k) и O(d·(n + b))
2 задачи
STR
Структура данных
Суффиксный массив
Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям.
O(n log n)
2 задачи