План лекций

Строки: база, полиномиальные хеши (14 октября 2024)

Определения: подстрока, суффикс, префикс, период
Поиск подстроки в строке
1. C++ : string.find(string), O(n²) ; слова про AVX
2. Префикс функция и КМП
3. Z-функция
Алгоритм Боера-Мура'77 (и его модификация Чжу-Такаоки'87)
Полиномиальный хеш строки
1. Цель: отобразить строки в целые числа, чтобы сравнивать их на равенство за O(1)
2. Вычисление хеша: h[i+1] = h[i]*P + s[i] ; substr(i, len) = h[i+len] - h[i]*deg[len]. При P > |Σ| инъекция. А теперь вычисления делаем по модулю.
3. Коллизии: Pr(s₁,...,s_n различны → h₁,...h_n различны) ≥ 1 - n(n-1)/(2M)
Хеши: использование
1. Алгоритм Рабина-Карпа c O(1) памяти
2. Наибольшая общая подстрока двух строк за O(nlogn).
LCP : O(n²), O(1)

− Перерыв −

Хеши, вероятности
1. Lm: если (P,MOD) фиксировано, MOD простое, мы берём случайный многочлен, то вероятность, что P − корень, равна 1/MOD
2. Lm: если многочлен и MOD фиксированы, MOD простое, мы берём случайное P, то вероятность, что P − корень, ≤ degree/MOD
3. Lm: если MOD фиксирован, MOD простое, мы берём случайное P и случайный многочлен, то вероятность, что P − корень равна 1/MOD
4. Анонс "строка Туэ-Морса", "тест против (P,MOD)-хеша".
5. Что делать с коллизиями? Выбирать случайную точку P или случайный простой MOD! Лучше P.
Хеши: теория
1. В C++ есть встроенный unordered_set<string>; hash<string>().
2. Lm: сколько корней у случайного многочлена? Ответ: 1
3. Всё-таки, нужна ли простота? По не простому модулю у многочлена может быть очень много корней. Пример: x³² ≡ 0(mod 2³²).
4. Окончание доказательства:
  1. Случай не случайных строк (следствие из леммы 2) получаем "длина строки"/M
  2. Случай случайных строк (следствие из леммы 3) получаем 1/M
Хеши: антихешовые тесты
1. Строка Туэ-Морса (__builtin_popcount(i) mod 2, или рекурсивно: S_n = S_n-1 + not S_n-1). Оценка длины строки, чтобы была коллизия.
2. [skipped] Тест против (P,MOD)-хеша. Алгоритм Капуна.