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

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

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

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

Забыто:

X[v] - Множество найденных образцов при попадании в вершину бора v. Предподсчёт размеров |X[v]|. Общее время работы алгоритма Ахо-Корасик O(sum Pi + T) с выдачей вхождений в сжатом виде.