Суффиксный автомат (19 сентября 2017)

  1. Определение, связь с суффиксным деревом, единственность, конечные вершины
    1. Суфавтомат = минимальный по числу вершин ДКА A: L(A) = {суффиксы строки}.
    2. Ещё раз определяем правый контекст в произвольном ДКА: Rs(vertex) = {x | из vertex по x мы попадём в терминал}. И для суффавтомата: Rs(u) = {x | ux − суффикс s}.
    3. Определим VA = {u | Rs(u) = A} − все строки с правым контекстом A. Заметим, что каждому классу VA должна соответствовать какая-то вершина автомата.
    4. Рёбра между классами проводятся однозначно: x ∈ A, xc ∈ B ⇒ между A и B есть ребро по символу "c"
    5. Устройство классов VA. Lm 1: Rs(v) = Rs(u) ⇒ v и u суффиксы друг друга, Lm 2: рассмотрим суффиксы строки v, получим цепочку вложенных классов.
    6. Какие вершины являются конечными? Определим last, len[V] (максимум), minLen[V], suf[V]. Получили ответ: last, suf[last], suf[suf[last]], ...

  2. Онлайн алгроитм построения за O(n)
    1. Что будем поддерживать? start, last, suf[v], len[v], next[v,c] (рёбра)
    2. База: s = ε start = last = 1
    3. Переход s → sa ⇒ Rs(v) = {z1, ..., zk} → Rsa(v) = {z1a, ..., zka} +? ε
    4. В каких случаях добавляется ε? v − суффикс sa.
    5. Что произойдёт с вершинами? Добавится новая: sa ∈ V{ε}. Строки из разных классов не могли оказаться в одном. Строки из одного могли оказаться в разных!
    6. Что произойдёт с рёбрами? Если два класса VA, VB не поменялись, наличие ребра между ними осталось. Поменяются только рёбра смежные с изменившимися вершинами.
    7. Rs(x) = Rs(y), Rsa(x) ≠ Rsa(y), x ≤ y ⇒ x − суффикс sa, y − не суффикс sa
    8. Рассмотрим z − самый длинный суффикс sa: v[z] = VRs(z) разделится. Тогда {suf[v[z]], suf[suf[v[z]]], ...} = {всех суффиксов sa}.
    9. Т.е. доказали, что если что-то разделится, то только v[z]. Как её найти? Суффикс sa = суффикс s + символ a. Будем перебирать суффиксы s.
    10. last, suf[last], suf[suf[last]]... если нет ребра по символу "a", пропускаем. Первое ребро по символу "a" ведёт из p в q=v[z].
    11. Правда ли, что все строки в q являются суффиксами sa? Самый длинный суффикс sa в q имеет длину len[p]+1, самая длинная строка в q имеет длину len[q]. Сравним.
    12. Раздваивание вершины: newQ = суффиксы sa, q = не суффиксы sa. Рёбра по "a" из части цепочки выше p направим в newLast, рёбра по "a", шедшие в q, направим в newQ.

  3. Написание алгоритма: (e-maxx)

  4. Оценка размера автомата
    1. Не более 2n вершин
    2. Не более (2n-1) + (n-1) = 3n-2 рёбер

  5. Оценка времени работы
    1. Потенциал длина суффиксной цепочки last, suf[last], suf[suf[last]], ...
    2. Изменение: часть длины ti заменили на часть длины 1, общий префикс уменьшился по принципу Дирихле

  6. ?