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

  1. [5 минут] Решение суфф массивом задач
    1. Напоминание, что суффмассив весит O(n) и мы его умеем строить хешами за O(nlog2n)
    2. Поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)

  2. [35 минут] Суффиксный массив за O(nlogn)
    1. Сортируем циклические сдвиги строки s#
    2. За O(Σ + n2) цифровой сортировкой
    3. От k переходим не к k+1, а к 2k, внутри используем сортировку подсчётом для пар, уже отсортированных по второй половине
    4. Учимся писать. Должно получиться что-то типа моего .

  3. [10 минут] Алгоритм Касаи LCP за O(n)
− Перерыв −
  1. [25 минут] Суффиксный массив за O(n). Алгоритм Каркайнена-Сандерса.
    1. Условие входа в функцию: дана строка длины n над алфавитом не более 2n.
    2. Новый алфавит − тройка подряд идущих символов. За O(n) цифровой сортировкой получили номера символов.
    3. SA(s): SA(s0s1) + Sort(s2) + Merge(s0s1, s2).
    4. Оценки времени: T(n) = O(n) + T(2n/3) + O(n) + O(n) = O(n).

  2. [15 минут] Алгоритм поиска подстроки в тексте за O(|s| + log|T|)
    1. Собственно алгоритм: SM ≥ max(min(SL, ML), min(SR, MR))
    2. Вычисление ML и MR за O(1) с предподсчётом за O(n): дерево отрезков
    3. Доказательство того, что при SM++ увеличится на следующей фазе max(SL, SR)