Изменения
Новая страница: «Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстр…»
Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование.
Давайте сначала определимся с методом хеширования.
Выберем полиномиальный хеш - <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>O(1)</tex>:
<tex>hash(s[i + 1..i + m - 1]) = hash(s[i..i + m - 1]) - p^{m - 1} s[i]</tex>.
<tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i + 1..i + m]) + 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>hash(s[1..m])</tex> и <tex>hash(p[1..m])</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>.
Псевдо-код:
'''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 := p <tex>\cdot</tex> h - <tex>p^{m}</tex>s[i] + s[i + m]
'''8:''' return not found
7 строка была получена с помощью быстрого пересчёта хеша. Мы считаем, что <tex>s[n + 1]</tex> - пустой символ.
Посчитаем время работы.
Изначальный подсчёт хешей - <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций - каждая выполняется за <tex>O(1)</tex>. Итого - <tex>O(n + m)</tex>.
Давайте сначала определимся с методом хеширования.
Выберем полиномиальный хеш - <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>O(1)</tex>:
<tex>hash(s[i + 1..i + m - 1]) = hash(s[i..i + m - 1]) - p^{m - 1} s[i]</tex>.
<tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i + 1..i + m]) + 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>hash(s[1..m])</tex> и <tex>hash(p[1..m])</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>.
Псевдо-код:
'''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 := p <tex>\cdot</tex> h - <tex>p^{m}</tex>s[i] + s[i + m]
'''8:''' return not found
7 строка была получена с помощью быстрого пересчёта хеша. Мы считаем, что <tex>s[n + 1]</tex> - пустой символ.
Посчитаем время работы.
Изначальный подсчёт хешей - <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций - каждая выполняется за <tex>O(1)</tex>. Итого - <tex>O(n + m)</tex>.
