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

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

1. Алгоритм Боера-Мура'77 (и его модификация Чжу-Такаоки'87!)
2. Полиномиальный хеш строки
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)
3. Хеши, вероятности
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.