Строки: полиномиальные хеши, суффиксный массив (16 октября 2017)

  1. Хеши: использование
    1. LCP хешами за [O(n), O(logn)]
    2. Наибольшая общая подстрока двух строк за O(nlogn).
  2. Суффиксный массив
    1. За O(n2logn) sort-ом
    2. За O(nlog2n) sort-ом с хешовым компаратором
    3. Решение суфф массивом задачи про поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)
− Перерыв −
  1. Суффиксный массив за O(nlogn)
    1. Сортируем циклические сдвиги строки s#
    2. За O(Σ + n2) цифровой сортировкой
    3. От k переходим не к k+1, а к 2k
    4. Учимся писать
  2. Алгоритм Касаи LCP за O(n)

  3. Суффиксный массив за 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)
  4. Алгоритм поиска подстроки в тексте за O(|s| + log|T|)