Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа — различия между версиями
Строка 1: | Строка 1: | ||
Алгоритм Рабина — Карпа — это алгоритм поиска подстроки в строке, используя хеширование. | Алгоритм Рабина — Карпа — это алгоритм поиска подстроки в строке, используя хеширование. | ||
− | + | ===Метод хеширования=== | |
Выберем полиномиальный хеш - <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])</tex> mod <tex>r</tex>, где <tex>p</tex> - это некоторое простое число, а <tex>r</tex> - некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически - при переполнении типов;). Заметим, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны. | Выберем полиномиальный хеш - <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])</tex> mod <tex>r</tex>, где <tex>p</tex> - это некоторое простое число, а <tex>r</tex> - некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически - при переполнении типов;). Заметим, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны. | ||
Строка 13: | Строка 13: | ||
Получается : <tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]</tex>. | Получается : <tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]</tex>. | ||
− | + | ===Алгоритм=== | |
У нас есть шаблон - <tex>p[1..m]</tex>. У нас есть строка - <tex>s[1..n]</tex>. Мы хотим найти все вхождения шаблона в строку. | У нас есть шаблон - <tex>p[1..m]</tex>. У нас есть строка - <tex>s[1..n]</tex>. Мы хотим найти все вхождения шаблона в строку. |
Версия 06:16, 26 сентября 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 строка была получена с помощью быстрого пересчёта хеша. Мы считаем, что
- пустой символ.Посчитаем время работы.
Изначальный подсчёт хешей -
. В цикле всего итераций - каждая выполняется за . Итого - .Литература
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.