Строки-4, Укконен, суффиксный автомат (22 апреля)

  1. Алгоритм Укконена
    1. Общая модель online-алгоритма: строка растёт, суффиксы растут
    2. Бесконечно растущий лист
    3. Основная тема: если суффикс разветвился, то все более длинные тоже разветвились
    4. Схема алгоритма: у нас есть указатель на самый длинный неразветвившийся суффикс, дописываем в конец строки один символ, указатель или спустится вниз, или перейдёт по суффиксной ссылке
    5. Чтобы алгоритм работал за линию достаточно быстро считать суффиксные ссылки
    6. Алгоритм подсчёта ссылок такой же, как в дереве палиндромов
    7. Доказательство линейности времени: потенциал − количество вершин на пути до корня
  2. Суффиксный автомат: общие слова
    1. Детерменированный автомат. Автомат, который принимает суффиксы строки. Минимальность.
    2. Делаем из суффиксного дерева суффиксный автомат − сжимаем одинаковые поддеревья.
    3. Принципиальное преимущества над суффиксным деревом: суффиксный автомат в несжатом виде имеет не более 2n вершин.
  3. Суффиксный автомат: алгоритм построения
    1. По каждой подстроке исходной мы из стартовой перейдём в некую вершину. Для каких подстрок мы перейдём в одну и ту же вершину? Правые контексты.
    2. Построение суффиксного автомата − online алгоритм. Пусть уже есть автомат для строки w, построим автомат для строки wa, какие правые контексты поменялись? Окажется, что изменений в среднем O(1).
    3. Леммы
      1. R(v) = R(u), |u| ≤ |v| ⇒ u − суффикс v
      2. u − суффикс v, R(v) ⊂ R(u)
      3. [не успеем] Rwa(v) = Rw(v)a + возможно пустая строка
      4. [не успеем] Если к R(v) добавилась пустая строка, то v − суффикс wa.
      5. [не успеем] ∃ самый длинный суффикс z, который встречался ранее.