Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. 
Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово 
в окошечке с заданным
образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах 
длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только 
если значения одинаковы, нужно проверять совпадение по буквам.
В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в 
окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. 
Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а 
лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было 
рассчитать, как меняется функция.
Привести пример удобной для вычисления функции.
Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной
функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.)
Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае 
может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из 
них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией 
ему бороться.)
Привести пример семейства удобных функций.
Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. 
Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти 
числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по 
модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом,
своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), 
умножению на x и добавлению свободного члена.
Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано
и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены 
(мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). 
Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их 
разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, 
если и много меньше p, то случайному x мало шансов попасть в неудачную точку.
.

Код прислал Вася Пупкин. :)