308
правок
Изменения
Добавлен пример строки когда алгоритм не работает
Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций, каждая выполняется за <tex>O(1)</tex>. Итоговое время работы алгоритма <tex>O(n + m)</tex>.
== Надёжность ==
Если количество подстрок данной строки близко к количеству хешей, то наступление [[Разрешение_коллизий | коллизий]] очень вероятно. Но даже при относительно небольших строках возможны частые ложные срабатывания.
Например если взять <tex> r = 2^{32}, p = 237 </tex>, за <tex> s </tex> принять [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex> 1024 </tex> , то алгоритм находит лишние вхождения почти в половине случаев.
== Примечания ==
<references>
</references>
== Литература ==
==Ссылки==
*[[Наивный алгоритм поиска подстроки в строке]]
*[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория: Хеширование]]
