Алгоритм Рабина-Карпа

Поиск подстроки в строке   7 января 2012  Автор статьи:  

Нам нужно проверить, входит ли данная строка в данный текст, и если входит, то начиная с какого символа текста.

Алгоритм решения

Итак, пусть у нас есть текст, состоящий из n символов, который в дальнейшем договоримся называть T, а T[i] его i-ый символ. Строку или просто слово, состоящее из m символов, назовем S, где S[i] -i-ый символ строки.

Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка Dm, где D — количество различных символов), и работать с ними будет так же неудобно.

Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы. В математике используется идея производить все арифметические действия по модулю какого-то простого числа (постоянно брать остаток от деления на это число). Таким образом, находится не само число, характеризующие строку, а его остаток от деления на некое простое число. Теперь мы ставим число в соответствие не одной строке, а целому классу, но так как классов будет довольно много (столько, сколько различных остатков от деления на это простое число), то дополнительную проверку придется производить редко.

Но всё же, нам приходётся производить сравнение строк посимвольно, но так как «холостых» срабатываний будет немного (в 1/P случаях,когда остатки от деления на простое число совпадут, где Р-выбранное простое число), то ожидаемое время работы малое. Вообще говоря, время работы есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Например,числа 9941 более чем достаточно даже для больших текстов.

  • Слава Муравьев

    Обычно в Рабине-Карпе используют полиномиальное хеширование строк, вычисляя хеш всех префиксов строки:

    h[i] = (s[0] * p[0] + s[1] * p[1] + … + s[i] * p[i]) % md, s — строка, p — степени какого-либо числа (главное условие к p — НОД(p, md) = 1; ну и чем больше, тем лучше), md — число, по которому берется остаток.

    Так вот, часто в целях ускорения работы программы, md делают равным 2^64. Чем это быстрее? А тем, что взятие по модулю 2^63 равносильно переполнению long в Java (long long в C++).
    То есть хеши просто последовательно вычисляются, не обращая внимание на переполнение типа. При таком подходе шанс совпадения хешей двух строк очень мал, так как различных остатков от деления на 2^63 примерно 9 * 10^18. Вдумайтесь, это же гигантское число, в реальности это означает, что при совпадении хешей вы на 99,99% можете быть уверены, что нашли нужную строку.

    Подробно про это описано в статье на хабре, посвященной полиномиальным хешам: http://habrahabr.ru/post/142589/

  • Слава Муравьев

    Обычно в Рабине-Карпе используют полиномиальное хеширование строк, вычисляя хеш всех префиксов строки:

    h[i] = (s[0] * p[0] + s[1] * p[1] + … + s[i] * p[i]) % md, s — строка, p — степени какого-либо числа (главное условие к p — НОД(p, md) = 1; ну и чем больше, тем лучше), md — число, по которому берется остаток.

    Так вот, часто в целях ускорения работы программы, md делают равным 2^64. Чем это быстрее? А тем, что взятие по модулю 2^63 равносильно переполнению long в Java (long long в C++).
    То есть хеши просто последовательно вычисляются, не обращая внимание на переполнение типа. При таком подходе шанс совпадения хешей двух строк очень мал, так как различных остатков от деления на 2^63 примерно 9 * 10^18. Вдумайтесь, это же гигантское число, в реальности это означает, что при совпадении хешей вы на 99,99% можете быть уверены, что нашли нужную строку.

    Подробно про это описано в статье на хабре, посвященной полиномиальным хешам: http://habrahabr.ru/post/142589/

Научиться программировать

  • на Delphi

  • на Java

  • на C++