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

  1. Суффиксный массив за O(nlogn)
    1. Сортируем циклические сдвиги строки s#
    2. За O(Σ + n2) цифровой сортировкой
    3. От k переходим не к k+1, а к 2k
    4. Учимся писать
  2. Алгоритм Касаи LCP за O(n)
  3. Алгоритм поиска подстроки в тексте за O(|s| + log|T|)
--- Перерыв ---
  1. Суффиксный массив за 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)