Полиномиальные хэш-функции

Июль 29, 2022

Главная
Информатика
Полиномиальные хэш-функции

Содержание

2. Определение
3. Рекурентное Определение
4. Основное Свойство
5. Пример
6. Поиск подстроки в строке 1/2
7. Поиск подстроки в строке 2/2 В худшем случае время O(sr). При случайном x и большом mod
8. Префикс-функция 1/2
9. Префикс-функция 2/2 Сложность: O(r + s log r). Сложность КМП: O(r + s). КМП заметно проще
10. Z-функция
11. S Неточный поиск подстроки 1/3 R Reverse(R) i i+r
12. Неточный поиск подстроки 2/3 Задача: для строк S и R найти вхождения в S всех строк,
13. Неточный поиск подстроки 3/3 Сложность: O(r + s K log r) Существует алгоритм за O(r +
14. Поиск минимального лексикографического сдвига строки Задача: для заданной строки S, среди всех ее циклических сдвигов, найти
15. Сортировка циклических сдвигов строки Задача: для данной строки S длины s отсортировать лексикографически все ее циклические
16. Полиномиальные хеши в матрицах
17. Поиск подматрицы в матрице
19. Скачать презентацию

Слайд 2

Определение

Слайд 3

Рекурентное Определение

Слайд 4

Основное Свойство

Слайд 5

Пример

Слайд 6

Поиск подстроки в строке 1/2

Слайд 7

Поиск подстроки в строке 2/2
В худшем случае время O(sr).
При случайном x

и большом mod при совпадении хешей можно опустить посимвольную проверку.
Для простоты вместо взятия модуля можно доверить переполнению unsigned long long.
Тогда в худшем случае время: O(s+r) и память O(s+r).
В точности равно сложности КМП.

Слайд 8

Префикс-функция 1/2

Слайд 9

Префикс-функция 2/2
Сложность: O(r + s log r).
Сложность КМП: O(r + s).
КМП

заметно проще в реализации.

Слайд 10

Z-функция

Слайд 11

S
Неточный поиск подстроки 1/3

R
Reverse(R)
i
i+r

Слайд 12

Неточный поиск подстроки 2/3
Задача: для строк S и R найти вхождения

в S всех строк, отличающихся от R не более, чем K символами.
Решение: пусть Q=substr(S, i, i + r), P=R
Найдем длину l1 максимального общего префикса Q и P. Очевидно, l1+1-ый символ различен.
Удалим первые l1+1 символов из обеих строк.
Повторим предыдущие два шага K раз, или пока P не станет равно R.
Если после j итераций строки равны, они имеют ровно j различных символов.

Слайд 13

Неточный поиск подстроки 3/3
Сложность: O(r + s K log r)
Существует алгоритм

за O(r + s K) или быстрее?

Слайд 14

Поиск минимального лексикографического сдвига строки
Задача: для заданной строки S, среди всех

ее циклических сдвигов, найти лексикографически минимальный.
Решение:
Приписать строку к самой себе;
Запомнить первую позицию как текущего кандидата;
Для каждой позиции начиная со второй улучшить кандидата, сравнив первый различный символ.
Сложность: O(s log s)
Сложность алгоритма Дюваля: O(s)

Слайд 15

Сортировка циклических сдвигов строки
Задача: для данной строки S длины s отсортировать

лексикографически все ее циклические сдвиги.
Решение:
Приписываем S к самой себе.
Сортируем массив [0..s-1).
Компаратор: первый различный символ двух сдвигов. Сложность компаратора: O(log s).
Сложность алгоритма: O(s log s log s).
Сложность суффиксных массивов: O(s log s)

Слайд 16