Изменения

[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худщем худшем случае - — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].

|definition = Пусть дана строка <tex>s[10..n-1]</tex>. Тогда '''полиномиальным хешем ''' (англ. ''polynomial hash'') строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[10..n-1]) = p^{n - 10} s[10] + ... + p^{0n - 1} s[n-1]</tex>, где <tex>p</tex> - — некоторое натуральное простое число, а <tex>s[i]</tex> <tex>{- }</tex> код <tex>i</tex>-ого символа строки <tex>s</tex>.

Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем <tex>{-}</tex> считать хеши по модулю <tex>r=2^{64}</tex> - некоторому большому числу (будем брать или <tex>r =2^{6432}</tex>), чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).

Использование полиномиального хеша именно с убывающими степенями Для работы алгоритма потребуется считать хеш подстроки <tex>s[i..j]</tex>. Делать это можно следующим образом: Рассмотрим хеш <tex>s[0..j]</tex>: <tex>\mathrm{hash}(s[0..j]) = s[0] + p s[1] +...+ p^{i-1} s[i-1] + p^{i} s[i] +...+ p^{j-1} s[j-1] + p^{j} s[j]</tex> Разобьем это выражение на две части: <tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + (p^{i} s[i] +...+ p^{j-1} s[j-1] + p^{j} s[j])</tex> Вынесем из последней скобки множитель <tex>p^{i}</tex> позволяет : <tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + p^{i}(s[i] +...+ p^{j-i-1} s[j-1] + p^{j-i} s[j])</tex> Выражение в первой скобке есть не что иное, как хеш подстроки <tex>s[0..i-1]</tex>, а во второй — хеш нужной намподстроки <tex>s[i..j]</tex>. Итак, мы получили, что: <tex>\mathrm{hash}(s[0..j]) = \mathrm{hash}(s[0..i-1]) + p^{i}\mathrm{hash}(s[i..j])</tex> Отсюда получается следующая формула для <tex>\mathrm{hash}(s[i..j])</tex>: <tex>\mathrm{hash}(s[i..j]) = (1/p^{i})(\mathrm{hash}(s[0..j]) - \mathrm{hash}(s[0..i-1]))</tex> Однако, зная как видно из формулы, чтобы уметь считать хеш некоторой строкидля всех подстрок начинающихся с <tex>i</tex>, посчитать нужно предпосчитать все <tex>p^{i}</tex> для <tex>i \in [0..n - 1]</tex>. Это займет много памяти. Но поскольку нам нужны только подстроки размером <tex>m</tex> <tex>{-}</tex> мы можем подсчитать хеш строки, образованной удалением первого символа и добавлением символа в конецподстроки <tex>s[0..m-1]</tex>, а затем пересчитывать хеши для всех <tex>i \in [0..n - m]</tex> за <tex>O(1)</tex>следующим образом:

Получается : <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{mi} s[i] + s[i + m]) \bmod r</tex>.

Алгоритм начинается с подсчета <tex>\mathrm{hash}(s[10..m-1])</tex> и <tex>\mathrm{hash}(p[10..m-1])</tex>, а также с подсчета <tex>p^{m}</tex>, для ускорения ответов на запрос.

Для <tex>i \in [10..n - m + 1]</tex> вычисляется <tex>\mathrm{hash}(s[i..i + m - 1])</tex> и сравнивается с <tex>\mathrm{hash}(p[10..m-1])</tex>. Если они оказались равны, то образец <tex>p</tex> скорее всего содержится в строке <tex>s</tex> начиная с позиции <tex>i</tex>, хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.

Для ускорения работы алгоритма оптимально Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки <tex>{-}</tex> выгоднее будет предпосчитать все степени <tex>p^{m}</tex>, а также хеши всех префиксов строки <tex>s</tex>.

'''int''' hashS = hash(s[10..m- 1]) '''int''' hashW = hash(w[10..m- 1]) '''for''' i = 1 0 '''to''' n - m + 1

===Пример худшего случая===Если количество подстрок данной строки превышает количество хешей (а это выполняется тогдаОднако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, когда длина строки больше то в худшем случае итоговое время работы алгоритма будет <tex>rO(n</tex>, так как количество различных значений полиномиального хеша совпадает с <tex>r\cdot</tex><tex>m), то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания</tex>.

Например, возьмем за <tex>S</tex> [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces== Сравнение с другими алгоритмами ==Преимущества: Anti-hash test]</ref> длиной * Быстрая скорость работы — <tex>2^{k}O(n + m)</tex>, где <tex>r = 2^{64}n</tex>— длина строки, <tex>pm</tex> - любое просто число. — длина образца;* Простая и понятная реализация;

Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>S'_k</tex> инвертированную строку <tex>S</tex>.  Покажем, что при <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>S'_k</tex> встретятся в б''о''льших строках много-много раз. Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Можно смело заменить коды символов на нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на <tex>\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i</tex>. Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(S'_k)</tex>? Нетрудно сообразить, что эта величина есть: <tex>T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}</tex>. То есть это знакопеременная сумма степеней <tex>p</tex>, где знаки чередуются по тому же правилу, что и символы в строке. Будем последовательно выносить из этой суммы множители за скобкуНедостатки: <tex>T = (p^{1} - 1)( - p^{0} + p^{2} + p^{4} - p^{6} + p^{8} - p^{10} - p^{12} + p^{14} ...) = </tex> <tex> = (p^{1} - 1)(p^{2} - 1)(p^{0} - p^{4} - p^{8} + p^{12} ...) = ... = (p^{1} - 1)(p^{2} - 1)(p^{4} - 1) ... (p^{2^{k-1}} - 1).</tex> Покажем, что <tex>T</tex> <tex>\mathrm{mod}</tex> <tex>r = 0</tex>: Нужно понять, на какую максимальную степень двойки делится каждая из <tex>k - 1</tex> скобок. Заметим, что <tex>(i + 1)</tex>-ая скобка <tex>p^{2^{i + 1}}  -  1 = (p^{2i}  -  1)(p^{2i}  +  1)</tex> делится на <tex>i</tex>-ую и ещё на какое-то чётное число <tex>p^{2i}  +  1</tex>. Это означает, что если <tex>i</tex>-ая скобка делится на <tex>2^r</tex>, то <tex>(i + 1)</tex>-ая скобка делится по меньшей мере на <tex>2^{r + 1}</tex>. Получается, что <tex>(p^1 - 1)(p^2 - 1)(p^4 - 1)...(p^{2k - 1}  -  1)</tex> делится по меньшей мере на <tex>2 \cdot 2^2 \cdot 2^3 \cdot ...  =  2^{k(k - 1) / 2}</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут. == Сравнение с другими алгоритмами ===== Преимущества ===* Быстрая скорость работы - <tex>O(n + m)</tex>, где <tex>n</tex> - длина строки, <tex>m</tex> - длина образца.* Простая и понятная реализация.=== Недостатки ===* Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая).;