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


Что: Семинар
Когда: Суббота, 17 февраля 2018, 16:20–17:40
Где: НГУ, ауд. 2128

Описание

Тандемные повторы (ТП). Поиск подстрок такого вида. Тривиальное решение за 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) с выдачей вхождений в сжатом виде.

Видео