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

1. Определения: подстрока, суффикс, префикс, период
2. Поиск подстроки в строке
1. C++ : string.find(string), O(n²)
2. Префикс функция
3. Z-функция


3. Алгоритм Боера-Мура'77 (и его модификация Чжу-Такаоки'87!)


4. Полиномиальный хеш строки
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)


5. Хеши, вероятности
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. Хеши: теория
1. В C++ есть встроенный unordered_set<string>; hash<string>().
2. Lm: сколько корней у случайного многочлена? Ответ: 1
3. Всё-таки, нужна ли простота? По не простому модулю у многочлена может быть очень много корней. Пример: x³² ≡ 0(mod 2³²).
4. Окончание доказательства:
1. Случай не случайных строк (следствие из леммы 2) получаем "длина строки"/M
2. Случай случайных строк (следствие из леммы 3) получаем 1/M


2. Хеши: антихешовые тесты
1. Строка Туэ-Морса (__builtin_popcount(i) mod 2, или рекурсивно: S_n = S_n-1 + not S_n-1). Оценка длины строки, чтобы была коллизия.
2. [skipped] Тест против (P,MOD)-хеша. Алгоритм Капуна.


3. Хеши: использование
1. Алгоритм Рабина-Карпа
2. Наибольшая общая подстрока двух строк за O(nlogn).