Семинар 2. Поиск тандемных повторов, Ахо-Корасик (Алгоритмы и структуры данных, часть 2, весна 2018)

Тандемные повторы (ТП). Поиск подстрок такого вида. Тривиальное решение за O(N^3). Ответ в сжатом виде. Поиск подстрок-ТП. Метод разделяй и властвуй. Пересекающие середину ТП = центр либо слева(*), либо справа, либо ровно посередине. Перебор длины ТП и условия на наличие ТП (через LCP). Определение LCP через Z-функции. Пакет ТП (размера O(N)). Общее время работы O(N log N).
Автомат Ахо-Корасик. Обработка символа за O(1) в худшем случае. Предподсчёт переходов из каждой вершины бора по каждому символу. Вычисление в порядке обхода в ширину за O(С * sum Pi). X[v] - Множество найденных образцов при попадании в вершину бора v. Предподсчёт размеров |X[v]|. Общее время работы алгоритма Ахо-Корасик O(sum Pi + T) с выдачей вхождений в сжатом виде.
Семинар №2 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов

[minmanr]

Непонятно, зачем третью задачу (количество строк длины L, содержащих заданный шаблон) решать через динамическое программирование и КМП, а не использовать чисто комбинаторные методы (подсчитать количество размещений с повторениями всех символов заданного алфавита с количеством позиций "L минус длина шаблона", с перебором всех возможных начальных позиций для вхождения шаблона).