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

1. Построение за O(n)
1. Определение суффиксного автомата. Тривиальное построение - минимизация дерева.
2. R(вершины) = R_s(строки). Вершина авотмата: R_s(v), ребро по букве z: R_s(v) → R_s(vz)
3. Вершина автомата = пачка (отрезок) суффиксов.
4. SA(s) → SA(sa): R_sa(v) = {xa | x ∈ R_s(v)} +? ε, где ε - пустая строка, а добавление идёт, если v - суффикс sa
5. SA(s) → SA(sa): разобьётся на две не более чем одна вершина, которую можно найти в цепочке, next[last,a] → next[suf[last],a],→ next[suf[suf[last]],a], ..., где last=R_s(s).
6. suf[x], len[x], собственно алгоритм


2. Оценка времени работы и размера
1. При цикле for: last → suf[last] → suf[suf[last]] → p уменьшается длина цепочки суфссылок
2. При переходе p → q, длина цепочки суфссылок может только уменьшиться
3. При цикле for: q → suf[q] → suf[suf[q]]... уменьшается длина цепочки суфссылок