Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа — различия между версиями
(Новая страница: «Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстр…») |
|||
Строка 21: | Строка 21: | ||
И для <tex>i \in [1..n - m + 1]</tex> считаем <tex>hash(s[i..i + m - 1]</tex> - сравниваем с <tex>hash(p[1..m])</tex>. Если они получаются равными - то мы считаем, что подстрока <tex>p</tex> входит в строку <tex>s</tex> (начиная с позиции <tex>i</tex>;). | И для <tex>i \in [1..n - m + 1]</tex> считаем <tex>hash(s[i..i + m - 1]</tex> - сравниваем с <tex>hash(p[1..m])</tex>. Если они получаются равными - то мы считаем, что подстрока <tex>p</tex> входит в строку <tex>s</tex> (начиная с позиции <tex>i</tex>;). | ||
− | Следует | + | Следует предподсчитать - <tex>p^{m}</tex>. |
Псевдо-код: | Псевдо-код: |
Версия 03:59, 17 марта 2011
Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование.
Давайте сначала определимся с методом хеширования.
Выберем полиномиальный хеш -
mod , где - это некоторое простое число, а - некоторое большое число, чтобы было меньше коллизий (обычно берётся или , чтобы модуль брался автоматически - при переполнении типов;). Заметим, что если 2 строчки имеют одинаковый хэш, то они с большой вероятностью равны.Научимся переходить от одного хеша к другому за
:.
.
Получается :
.Теперь к самому алгоритму.
У нас сеть шаблон -
. У нас есть строка - . Мы хотим найти все вхождения шаблона в строку.Давайте посчитаем
и .И для
считаем - сравниваем с . Если они получаются равными - то мы считаем, что подстрока входит в строку (начиная с позиции ;).Следует предподсчитать -
.Псевдо-код:
1: function RabinKarp(string s[1..n], string p[1..m]) 2: hp := hash(p[1..m]) 3: h := hash(s[1..m])ы 4: for i from 1 to (n-m+1) 5: if h = hp 6: add i 7: h := ph - s[i] + s[i + m] 8: return not found
7 строка была получена с помощью быстрого пересчёта хеша. Мы считаем, что
- пустой символ.Посчитаем время работы.
Изначальный подсчёт хешей -
. В цикле всего итераций - каждая выполняется за . Итого - .