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

Алгоритм основан на простой идее. Представим себе, чтов слове длины m мы ищем образем длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.

При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Заменим все буквы в слове и образце их номерами оrd(), представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа.

Пример:
Пусть Алфавит и коды :
Q = 1
W = 2
E = 3
R = 4
T = 5
Y = 6

Подстрока: QWERTY
Строка: QWERYTEWEQWERTY

Считаем хэш-функцию для подстроки: SS = 1+2+3+4+5+6 = 21

QWERYTEWEQWERTY

Считаем хэш-функцию для первых 6 символов строки: FS = 1+2+3+4+6+5 = 21

Проводим полное сравнение строк - строки не совпадают. Сдвиг на 1 позицию.

QWERYTEWEQWERTY

FS = 21 - [Q] + [E] = 21 - 1 + 3 = 23 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 23 - [W] + [W] = 23 - 2 + 2 = 23 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 23 - [E] + [E] = 23 - 3 + 3 = 23 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 23 - [R] + [Q] = 23 - 4 + 1 = 20 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 20 - [Y] + [W] = 20 - 6 + 2 = 16 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 16 - [T] + [E] = 16 - 5 + 3 = 14 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 14 - [E] + [R] = 14 - 3 + 4 = 15 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 15 - [W] + [T] = 15 - 2 + 5 = 18 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 18 - [E] + [Y] = 18 - 3 + 6 = 21 - код совпадает, полное сравнение совпадает.

Рассмотрим другие функции хеширования. Хорошие фунцции хэширования должны удовлетворять следующим требованиям:

1. Легко вычисляться.

2. Как можно лучше различать несовпадающие строки.

3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ] ):
hash( y[ i+1 , i+m ] ) = rehash( y[ i ], y[ i+m ], hash( y[ i , i+m-1]).

Пусть функция будет определена для слова w, например, следующим образом:

hash( w[ 0 , m-1 ] ) = ( w[0] * 2 ^m-1 + w[1] * 2 ^m-2 + ... + w[m-1] ) mod q,

где q - большое число. Тогда

rehash( a, b, h ) = (( h - a * 2 ^m-1 ) * 2 + b) mod q.

Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.
Ожидаемое время работы малое O(m+n+mn/q), сложность работы почти линейная.
Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками. Данный алгоритм один из самых быстрых при одновременном поиске нескольких образцов.