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

Ахо-Корасик как обобщение КМП. Что ищет поиск? Множество префиксов = узлы бора. FF-цепочка узла. Вычисление FF через BFS и лениво. Время работы. Сжатая функция отката. (TODO: выяснить, на какой паре это надо рассказывать)

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

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