Сколько разных кусков
Насколько последовательность ДНК разнообразна? Один из способов ответить — посчитать, сколько в ней разных кусков: у ACGT все десять кусков разные, а у AAAA — только четыре: A, AA, AAA и AAAA. Повторы уменьшают это число, и чем длиннее и чаще повторы, тем сильнее. Биологи называют такую меру лингвистической сложностью последовательности; её предложил Эдвард Трифонов в 1990 году.
Для каждой строки найдите число её различных непустых подстрок — кусков, идущих подряд. Одинаковые куски в разных местах считаются один раз.
Среди тестов — геном фага лямбда (48 502 буквы), митохондрия человека, фаг φX174, теломера из одного повторённого звена и слово Фибоначчи.
Вход
В первой строке число строк t (1 ≤ t ≤ 1000). В каждой из следующих t строк — непустая строка из латинских букв. Суммарная длина строк не больше 100 000.
Выход
Для каждой строки — число её различных подстрок. Ответ может не поместиться в 32 бита.
Примеры
Пример 1
3 abracadabra ACGT AAAA
54 10 4
Пример 2
2 TTAGGGTTAGGG GATTACA
53 25
Ограничения
- Время · Python
- 7000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Подстрок всего n(n + 1)/2, и сложить их все в множество — это порядка n² памяти: на ста тысячах букв пять миллиардов кусков. Нужно считать повторы, не выписывая куски.
2Подсказка 2
Каждая подстрока — начало какого-то суффикса. Отсортируйте суффиксы. Сколько новых подстрок даёт очередной суффикс, если начала, общие с предыдущим в порядке сортировки, уже посчитаны?
3Идея
В суффиксном массиве суффикс номер j даёт столько новых подстрок, сколько у него начал, которых не было у суффиксов выше, — его длина минус lcp[j], общее начало с соседом выше. Начало, общее с любым суффиксом выше, общее и с ближайшим соседом: в отсортированном списке общее начало двух суффиксов не длиннее общего начала каждого из них с любым суффиксом, стоящим между ними. Поэтому ответ — n(n + 1)/2 − Σ lcp[j].
4Разбор
Суффиксный массив удвоением, массив lcp алгоритмом Касаи, одна формула. Это те же функции, что в листинге статьи.
Посмотрите на ответы. У генома лямбды 1 175 898 383 разных куска из 1 176 246 253 возможных: повторов в нём почти нет, и не хватает лишь 0,03 %. У теломеры из ста тысяч букв разных кусков чуть меньше шестисот тысяч — каждый кусок однозначно задаётся длиной и сдвигом внутри звена. У ста тысяч букв A — ровно сто тысяч.
4+Решение
5Сложность
Удвоение — O(n log n), Касаи — O(n). Сравнивать соседей с первой буквы — O(n) на обычной ДНК, но на теломере каждый сосед совпадает с предыдущим почти целиком, и это около n²/2 сравнений.
6Типичные ошибки
- lcp наивно. Сумма общих начал соседей, посчитанная сравнением с нуля, на повторах квадратична. Касаи начинает каждое сравнение с h − 1, где h — общее начало предыдущего по тексту суффикса.
- 32 бита. Уже для лямбды ответ больше миллиарда, а в девятом тесте — больше четырёх миллиардов.
- Множество подстрок. Работает на коротких строках и съедает память на длинных.