Алгоритмы на строках: хеширование и KMP
Полиномиальные хеши для сравнения подстрок за O(1) и префикс-функция (KMP) для поиска образца.
Сравнивать подстроки посимвольно — O(n) на сравнение. Два инструмента снимают это ограничение.
Полиномиальный хеш: строке сопоставляется число h = s[0]·p^(k-1) + s[1]·p^(k-2) + ... по модулю. Предпосчитав префиксные хеши и степени p, хеш ЛЮБОЙ подстроки достаётся за O(1) — и равные подстроки имеют равные хеши. Разные подстроки теоретически могут совпасть хешем (коллизия), но при модуле ~10⁹ вероятность ничтожна, а для параноиков есть двойной хеш.
Сравнение подстрок хешами. Введите: abacaba 2, затем запросы «l1 r1 l2 r2»: 1 3 5 7 и 1 2 2 3
На примере: подстроки [1,3] и [5,7] строки abacaba — обе «aba» (YES), а [1,2] и [2,3] — «ab» и «ba» (NO).
Второй инструмент — префикс-функция: pi[i] — длина наибольшего собственного префикса строки, который одновременно её суффикс в позиции i. Считается за O(n) и лежит в основе алгоритма КМП: чтобы найти образец в тексте, склейте «образец # текст» и ищите позиции, где pi равна длине образца.
КМП: все вхождения образца. Введите: ababcab ab
На примере образец ab находится в ababcab на позициях 1, 3 и 6.
Сердце алгоритма — цикл while j = pi[j-1]: при несовпадении мы не начинаем сначала, а откатываемся к следующему кандидату-префиксу. Суммарно указатель j уменьшается не больше, чем увеличивается, — отсюда O(n).
Задание: с помощью префикс-функции найдите наименьший период строки (подсказка: n - pi[n-1], если n делится на это значение).
Отметьте урок пройденным.