В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2020
/

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

Суббота, 22 февраля 2020
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 16 записей
    1.
    Лекция 1. Строки. Z-функция
    2.
    Семинар 1. LCP, поиск палиндромов, ДКА
    3.
    Лекция 2. Префикс-функция, поиск бора
    4.
    Семинар 2. Поиск тандемных повторов, Ахо-Корасик
    5.
    Лекция 3. Суффиксное дерево
    6.
    Семинар 3. Эквивалентность автоматов
    7.
    Лекция 4. Суффиксный массив
    8.
    Семинар 4. Недетерминированные автоматы
    9.
    Лекция 5. Суффиксный массив (продолжение)
    10.
    Семинар 5. Регулярные выражения
    11.
    Лекция 6. Преобразование Барроуза-Уилера
    12.
    Семинар 6. Контекстно-свободные грамматики
    13.
    Лекция 7. Приближённый поиск подстроки
    14.
    Семинар 7. Контекстно-свободные грамматики
    15.
    Лекция 8. Графы, обход в ширину, обход в глубину
    16.
    Семинар 8. Разбор КС-грамматики

Описание

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

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

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

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