1632
правки
Изменения
м
rollbackEdits.php mass rollback
Разобьем это выражение на две части:
<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[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r</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>O(n + m)</tex>.
Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма буде будет <tex>O(n</tex> <tex>\cdot</tex> <tex>m)</tex>.
== Сравнение с другими алгоритмами ==
[[Категория:Поиск подстроки в строке]]
[[Категория: Хеширование]]
[[Категория:Точный поиск]]
