Суффиксный автомат и применения (20 февраля 2024)

1. [10 минут] Написание алгоритма
   
   
2. [10 минут] Оценка размера автомата
   1. Не более 2n вершин
   2. Не более (2n-1) + (n-1) = 3n-2 рёбер
   
   
3. [15 минут] Простейшие свойства
   1. Проверка, входит ли строка в текст.
   2. Количество раз, которое строка входит в текст. Find max refrain.
   3. Какая самая короткая/длинная строка заканчивается в вершине? first[v], endpos[v].
   
   
4. [20 минут] Применения
   1. LZSS за O(n)
   2. Поиск общей подстроки k строк построением автомата от минимальной
   
   
5. [25 минут] Th1. Автомат → Дерево.
   1. suf[u] лежит на пути до u в SufTree(rev(s))
   2. Построение рёбер дерева через автомат. Какая строка написана на ребре дерева?
   3. [skipped] Суффиксные ссылки суффиксного дерева
   4. [skipped] Th2. Дерево → Автомат. Расширенные суффссылки.
   
   
6. [skipped] [10 минут] Задачи
   1. [skipped] Перебор всех вхождений строки в текст за O(|s| + |answer|)
      1. [skipped] LCP обратной строки в суффиксном автомате: LCA в дереве суффссылок.
      2. [skipped] Задача: найти максимальный общий подпалиндром двух строк с автоматом, но без сжатого бора