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

  1. [15 минут] Простейшие свойства
    1. Проверка, входит ли строка в текст.
    2. Количество раз, которое строка входит в текст. Find max refrain.
    3. Какая самая короткая/длинная строка заканчивается в вершине? first[v], endpos[v].

  2. [30 минут] Применения
    1. Поиск общей подстроки k строк построением автомата от минимальной
    2. LZSS за O(n)

  3. [25 минут] Th1. Автомат → Дерево.
    1. suf[u] лежит на пути до u в SufTree(rev(s))
    2. Построение рёбер дерева через автомат. Какая строка написана на ребре дерева?
    3. [skipped] Суффиксные ссылки суффиксного дерева
  4. [skipped] Th2. Дерево → Автомат. Расширенные суффссылки.
  5. [10 минут] Задачи
    1. Перебор всех вхождений строки в текст за O(|s| + |answer|)
      1. LCP обратной строки в суффиксном автомате: LCA в дереве суффссылок.
      2. [skipped] Задача: найти максимальный общий подпалиндром двух строк с автоматом, но без сжатого бора
− Перерыв −
  1. Автоматы (повторение): эквивалентность, минимизация, детерминизация
    1. Изоморфизм автоматов
    2. Дан автомат, проверить, эквивалентен ли он суффиксному за O(n+m)?
    3. Даны два автомата, проверить на эквивалентность
      1. [skipped] bfs за O(nm)
      2. Через минимизацию
    4. Минимизация автоматов
      1. [skipped] Через детерминизацию (Алгоритм Бржозовского), детерминизация за O(answer)
      2. За O(nm) расщеплением классов.
      3. Алгоритм Хопкрофта за O(ElogV) расщеплением классов.