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

  1. Хеши: теория
    1. В C++ есть встроенный unordered_set<string>; hash<string>().
    2. Lm: сколько корней у случайного многочлена? Ответ: 1
    3. Всё-таки, нужна ли простота? По не простому модулю у многочлена может быть очень много корней. Пример: x32 ≡ 0(mod 232).
    4. Окончание доказательства:
      1. Случай не случайных строк (следствие из леммы 2) получаем "длина строки"/M
      2. Случай случайных строк (следствие из леммы 3) получаем 1/M
  2. Хеши: антихешовые тесты
    1. Строка Туэ-Морса (__builtin_popcount(i) mod 2, или рекурсивно: Sn = Sn-1 + not Sn-1). Оценка длины строки, чтобы была коллизия.
    2. Тест против (P,MOD)-хеша. Алгоритм Капуна.
--- Перерыв ---
  1. Хеши: использование
    1. Алгоритм Рабина-Карпа
    2. LCP хешами за [O(n), O(logn)]
    3. Наибольшая общая подстрока двух строк за O(nlogn).
  2. Суффиксный массив
    1. За O(n2logn) sort-ом
    2. За O(nlog2n) sort-ом с хешовым компаратором
    3. Решение суфф массивом задачи про поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)