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

Суббота, 22 февраля 2020
НГУ, ауд. 2128, НГУ, новый корпус

Описание

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

Замечание: с 2021 года Ахо-Корасик перенесён на семинар.

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

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