Автоматы (22-е апреля 2019)

  1. Оценка времени работы и размера
    1. от n+2 до 2n-1 вершин: добавляется не более 2, для n=2 вершин 3
    2. не более 3n-4 рёбер (V-1)+(n-2): короткие рёбра образуют дерево на всех вершинах, длинное ребро можно дополнить до суффикса короткими рёбрами справа и слева, все такие суффиксы различны и их не более n-2

  2. Задачи
    1. Число различных подстрок
    2. Сколько раз входит подстрока, самое левое вхождение подстроки
    3. Найти самую длинную строку, имеющую два непересекающихся вхождения
    4. LZSS
    5. Общая подстрока через SA(конкатенации) и SA(меньшей)

  3. Связь с суфдеревом
    1. В ребре суфдерева заканчиваются строки с одинаковым ЛЕВЫМ контекстом
    2. SA(s) = ST(reverse(s))
    3. Ребро суфдерева - отрезок строки: left=D[b]+Len[a], length=Len[b]-Len[a], где D[b] - длина любой строки из Rs(b)