Похожие презентации:
Строковые алгоритмы
1.
Строковые алгоритмыАвтор: Ефимов Егор Александрович
2.
Полиномиальное хешированиеХеш-функция сопоставляет объекту некоторое число.
Для вычисления хеша последовательности вида a1a2a3…an нужно
выбрать значение p - произвольное число большее, чем размер алфавита и
mod - модуль хеширования такие, что
|ai| < p < mod, gcd(p, mod) = 1
3.
Полиномиальное хешированиеПрямой полиномиальный хеш можно вычислить следующим образом:
h = (a1 + a2* p + a3* p2 + … + an - 1* pn - 1) % mod
Обратный полиномиальный хеш:
h = (a1 * pn - 1 + a2 * pn - 2 + … + an - 1 * p + an) % mod
Хеш вычисляется за O(N), N - длина строки.
4.
Полиномиальное хешированиеУчитывая, что хеш является значением многочлена, мы можем
быстро пересчитывать значение хеша от результата выполнения многих
строковых операций.
Так для вычисления хеша подстроки произвольной длины
(считается, что хеши на префиксах предпосчитаны) мы можем использовать
вычитание многочленов.
5.
Полиномиальное хешированиеПример. Дана последовательность a1a2a3a4a5. Получить значение хеша
подстроки a3a4a5.
Обратный полиномиальный хеш:
h[1:5] - h[1:2] * p3 = h[3:5]
h[1:5] = a1* p4 + a2* p3 + a3* p2 + a4* p + a5
h[1:2] = a1* p + a2
(a1* p4 + a2* p3 + a3* p2 + a4* p + a5) - (a1* p + a2)*p3 = a3* p2 + a4* p + a5
6.
Полиномиальное хешированиеОбщая формула для вычисления значения хеша на подотрезке (i, j),
h(i, j) = pr[ j + 1] - pr[ i ] * p j - i + 1
Формула предподсчёта значений хеша на префиксе:
pri + 1 = pri * p + ai
Вычисление хеша на любой подстроке будет выполняться за O(1).
7.
Полиномиальное хешированиеПрямой полиномиальный хеш:
(a1 + a2* p + a3* p2 + a4* p3 + a5* p4) - (a1 + a2* p) = a3* p2 + a4* p3 + a5* p4
Но хеш a3a4a5 равен:
a3 + a4* p + a5* p2
(a3 + a4* p + a5* p2) != (a3* p2 + a4* p3 + a5* p4)
Можно сделать так:
(a3* p2 + a4* p3 + a5* p4) * p-2
8.
Полиномиальное хешированиеВ общем виде
(h[ j + 1] - h[ i ]) * p-i)
Для этого требуется знать обратный элемент. Если модуль выбран простым,
то по теореме Эйлера мы сможем вычислить обратный элемент
pm - 2 = p-1 (mod m)
9.
Полиномиальное хешированиеЛибо мы можем фиксировать не младшую степень, а старшую.
Тогда
(h[ j + 1] - h[ i ]) * pn - j
Где n - максимальный размер строки. В таком случае не требуется
вычислять обратный элемент по модулю.
10.
Полиномиальное хеширование. Проверка на равенствоs = abcde → hs
t = abcde → ht
if (s == t) ⇒ hs == ht
if (hs == ht) ⇏ s == t
Несмотря на то, что из равенства хешей не следует равенство строк, этого
можно добиться с большой вероятностью, если правильно выбрать
пространство хеширования.
Выполняется за O(1)
11.
Полиномиальное хеширование. Сравнение набольше/меньше
Для сравнения на больше/меньше требуется найти первый несовпадающий
элемент слева, то есть найти минимальный префикс такой, что хеш от s и t
на этом префиксе будут различны.
1. Находим наибольший общий префикс. Если хеши предпосчитаны, то мы
можем сделать это бинарным поиском за O( log(min(len(s), len(t))) ).
2. Сравнить след. элемент за O(1).
Таким образом сравнение на больше/меньше выполняется за O(log(n))
12.
Полиномиальное хеширование. Уменьшениевероятности коллизий.
P = n2 / (2 * mod)
Чтобы решение работало как можно чаще, нужно увеличить пространство
хеширования.
Рассмотрим варианты, когда mod ~ 1018.
1. mod1 * mod2, mod1 && mod2 ∈ ℙ.
2. mod = 261 - 1 ∈ ℙ - самый быстрый вариант.
Также есть модуль 264 ∉ ℙ. Он удобен тем, что в C++ вычисления в типе
uint64_t (unsigned long long) - вычисления по модулю 264.
13.
Полиномиальное хеширование. Строка Туэ-Морса.При хешированию по модулю 264 строки вида
abbabaabbaababba…
В общем виде:
Si + 1 = Si + (~Si)
Произойдёт зануление хеша.
Подробнее здесь:
https://codeforces.com/blog/entry/4898?locale=en
14.
Полиномиальное хеширование. Обмен местами двухсимволов в полиномиальном хеше.
Дана последовательность
s1…si…sl…sk…sj…sn
Требуется вычислить хеш на отрезке [i, j] при условии, что sl и sk поменяли
местами.
s1…[si…sk…sl…sj]…sn
15.
Полиномиальное хеширование. Обмен местами двухсимволов в полиномиальном хеше.
Учитывая, что у нас были предпосчитаны хеши для начальной строки, мы
можем собрать хеш новой подстроки из тех кусочков, на которых хеши не
изменились:
s1…[si…sk…sl…sj]…sn
Будем считать, что мы вычислили длину не изменившихся блоков и она
равна m3, m2, m1.
hm1 + sl*pm1 + hm2*pm1 + 1 + sk*pm1 + 1 + m2 + hm3*pm1 + m2 + 2
16.
Полиномиальное хеширование. Применение1.
Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)
2.
Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O((n + m·log(n))·log(m)) и O(n·log(m))
3.
Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))
4.
Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)2)
5.
Нахождение количества подпалиндромов строки длины n за O(n·log(n))
6.
Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))
7.
Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением
всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз)
8.
Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))
17.
Полиномиальное хеширование. Полезные ссылкиhttps://codeforces.com/blog/entry/65819 - вычисление по модулю 261 - 1
https://pastebin.com/5Run2F5y - реализация хеша в виде структуры данных
https://e-maxx.ru/algo/string_hashes
https://codeforces.com/blog/entry/60445
18.
Z-функция строкиZ-функция - массив длины n, i-ый элемент которого равен наибольшему
числу символов, начиная с позиции i, совпадающих с первыми символами
строки S.
Иными словами Z[ i ] - это наибольший общий префикс строки S и её i-того
суффикса.
Первый элемент Z-функции, Z[0] обычно считается неопределённым.
19.
Z-функция. Тривиальный алгоритмПростая реализация выполняется за O(N2), где N - длина строки. Для каждой
позиции i перебираем для неё ответ, пока не обнаружим несовпадение или
не дойдём до конца строки.
vector<int> zFunction(s : string):
vector<int> zf(n);
for i = 1 to n − 1
while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]
zf[i]++
return zf
20.
Z-функция. Эффективный алгоритмНазовём Z-блоком подстроку с началом в позиции i и длиной Z[ i ]. Заведём 2
переменные: left и right - начало и конец Z-блока строки S, с максимальной позицией
конца right. Изначально left = 0, right = 0.
1. i > right: Пробегаем по строке S и сравниваем символы на позициях
S[i +j] и S[ j ]. Пусть j первая позиция для которой не выполняется
S[i +j] = S[ j ]. Тогда j это и Z-функция для позиции i. Тогда left = i, right = i + j - 1
2. i <= right: Сравним Z[i - left] + i и right. Если right <, то нужно наивно пробежаться
по строке начиная с позиции right и вычислить Z[ i ]. Иначе мы уже знаем верное
значение Z[ i ], т.к. оно равно Z[ i - left ].
Этот алгоритм работает за O(N), N - длина строки
21.
Z-функция. Ссылкиhttps://e-maxx.ru/algo/z_function - тут есть доказательство линейности
алгоритма
https://neerc.ifmo.ru/wiki/index.php?title=Z-функция
22.
Префикс-функцияДана строка s[0…n-1]. Требуется вычислить для неё префикс-функцию, т.е.
массив чисел π[0…n-1], где π[ i ] определяется как наибольшая длина
наибольшего собственного суффикса подстроки s[0…i], совпадающего с её
префиксом.
Значение π[0] полагается равным 0.
23.
Префикс-функция. Эффективный алгоритмЗаметим, что p[i+1] <= p[i]+1. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции i+1 и
имеющий длину p[i+1], удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции i
и имеющий длину p[i + 1] - 1.
Избавимся от явных сравнений строк. Пусть мы вычислили p[i], тогда, если s[i+1]=s[p[i]], то p[i+1]=p[i]+1. Если
окажется, что s[i+1]≠s[p[i]], то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу
перейти к такому бордеру наибольшей длины, для этого подберем такое k, что k=p[i]−1. Делаем это
следующим образом. За исходное k необходимо взять p[i−1], что следует из первого пункта. В случае, когда
символы s[k] и s[i] не совпадают, p[k−1] — следующее потенциальное наибольшее значение k, что видно из
рисунка. Последнее утверждение верно, пока k>0, что позволит всегда найти его следующее значение. Если
k=0, то p[i]=1 при s[i]=s[1] , иначе p[i]=0.
Время работы алгоритма составит O(n).
24.
Алгоритм Кнута-Морриса-ПраттаКМП предназначен для поиска шаблона (подстроки) в строке.
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
25.
Префикс-функция → Z-функция & V/V ~ O(N)Префикс-функция и Z-функция взаимозаменяемы и могут быть
представлены друг через друга за линейное время.
https://clck.ru/32jg2N - Построение префикс-функции по Z-функции
https://clck.ru/D3niW - Построение Z-функции по префикс-функции
26.
https://neerc.ifmo.ru/wiki/index.php?title=Основные_определения,_связанные_со_строками