Семинар 2. Поиск тандемных повторов, Ахо-Корасик

Тандемные повторы (ТП). Поиск подстрок такого вида. Тривиальное решение за O(N^3). Ответ в сжатом виде. Поиск подстрок-ТП. Метод разделяй и властвуй. Пересекающие середину ТП = центр либо слева(*), либо справа, либо ровно посередине. Перебор длины ТП и условия на наличие ТП (через LCP). Определение LCP через Z-функции. Пакет ТП (размера O(N)). Общее время работы O(N log N).

((Алгоритм Ахо-Корасик на примере. Множество префиксов = узлы бора. Ахо-Корасик как обобщение КМП, КМП = Ахо-Корасик с одним шаблоном. FF-цепочка узла. Что ищет поиск. Таблица соответствия КМП и Ахо-Корасик. Сжатая функция отката.))

Автомат Ахо-Корасик. Обработка символа за O(1) в худшем случае. Предподсчёт переходов из каждой вершины бора по каждому символу. Вычисление в порядке обхода в ширину за O(С * sum Pi).