раций за время 0(1) едва ли допустимо. К счастью, эту трудность можно обойти следующим образом: надо проводить вычисления чисел р и to, а также вычисления по формуле (34.1), по модулю фиксированного числа q (рис. 34.4; по поводу арифметики по модулю q см. разд. 33.1). Тогда все числа не превосходят q и можно считать, что число р и все tj будут действительно вычислены за время О (га + то). Обычно в качестве q выбирают простое число, для которого 10q помещается в машинное слово - это упрощает программирование вычислений. В общем случае (для алфавита { О, 1, 2,..., d }) выбирают такое простое число q, что dq помещается в машинное слово (благодаря этому все арифметические операции происходят в пределах одного слова); рекуррентное соотношение (34.1) приобретает вид

ts+1 = (d(ts - T[s + l]h) + T[s + то + 1]) mod q,(34.2)

где h = dm~l (mod q).

Вычисления по модулю q хороши всем, кроме одного: из равенства ts = р (mod q) ещё не следует, что ts = р. Поэтому, если ts ф р (mod q), то сдвиг s заведомо недопустим и о нем можно забыть, а если ts = р (mod q), то надо еще проверить, совпадают ли строки Р[1..то] и T[s+1..s+to] на самом деле. Если совпадают, то мы нашли вхождение образца в строку, а если не совпадают, то произошло холостое срабатывание (spurious hit). Если простое число q достаточно велико, то можно надеяться, что дополнительные затраты на анализ холостых срабатываний будут невелики.

Запишем текст соответствующей процедуры Rabin-Karp-Matcher. Она получает на вход текст Г, образец Р, «основание системы счисления» d (обычно берут d = Е) и простое число q.

Rab in-Karp-Mat cher(Т,P,d,q)

1n \gets length[T]

2m \gets length[P]

3h \gets d~{m-l} \bmod q

4p \gets 0

5t \gets 0

6for i \gets l to m

7do p \gets (dp+P[i]) \bmod q

8t \gets (dt+T[i]) \bmod q

9for s \gets 0 to n-m

10do if p=t

11then if P[l..m]=T[s+l..s+m]

12then print Образец входит со сдвигом s

13if s<n-m

14then t \gets (d(t-T[s+l]h) + T[s+m+l]) \bmod q

Опишем работу процедуры. Все символы рассматриваются как d-ичные цифры. В строках 1-5 переменным присваиваются началь-

Рис.34.4, занимающий целую страницу.

Переводы надписей, входящих в рисунок: valid match - вхождение образца, spurious hit - холостое срабатывание, old high-order digit - цифра старшего разряда, new low-order digit - цифра младшего разряда, shift не переводить и не воспроизводить (ни слово, ни стрелку).

Подпись:

Рис.34.4. Алгоритм Рабина-Карпа. У = { 0, 1, 2,..., 9 }, q = 13. (а) Строка Г (текст). Серым выделено окошко ширины 5. Численное значение выделенной подстроки равно 7 по модулю 13. (б) Для того же текста указаны численные значения (по модулю 13) всех подстрок длины 5. Если образец есть Р = 31415, то нас интересуют подстроки со значением 7, поскольку 31415 = 7 (mod 13). Таких подстрок всего две; одна из них соответствует вхождению образца в текст, а другая - холостому срабатыванию, (в) Изменение числового значения при сдвиге окошка. В предыдущем окошке стояло 31415. Удалив цифру старшего разряда и приписав новую цифру младшего разряда, получаем 14152. Те же вычисления по модулю 13 из старого значения 7 получают новое значение 8.

ные значения (h - это «единица старшего разряда» в й-ичной системе). В цикле в строках 6-8 с помощью схемы Горнера вычисляются значения р и to (последнее присваивается переменной t). Цикл в строках 9-14 перебирает все возможные значения s; в момент исполнения строки 10 имеем t = ts (mod q). Если оказывается, что ts = р, то строки T[s+ l..s + гаг] и Р[1..га] сравниваются и, в случае совпадения, об этом печатается сообщение (строки 11-12). Если ts ф р, то программа проверяет, будет ли цикл выполняться далее (строка 13), и если будет, то обновляет значение t по формуле (34.2) - строка 14.

В худшем случае эта процедура требует времени в ((га - га+1)га), как и простейший алгоритм - уже потому, что для всех допустимых сдвигов происходит посимвольная проверка. Например, если Р = ат и Т = а™, то сравнение в строке 11 будет выполняться для всех значений s (и алгоритм отличается от тривиального лишь в худшую сторону за счёт дополнительных затрат на вычисление h в строке 3, на цикл в строках 6-8 и на вычисления в строке 14).

Во многих приложениях следует ожидать, что допустимых сдвигов будет немного; в этом случае время работы алгоритма Рабина - Карпа будет О (га + гаг) плюс небольшие дополнительные затраты на обработку холостых срабатываний. Можно сделать нестрогую прикидку, основываясь на следующих соображениях. Будем считать, что отображение редукции по модулю q - случайная функция из Е* в Zq. Это утверждение трудно поддается формализации и доказательству, но эмпирически подтверждается (ср. разд. 12.3.1, где мы обсуждали применение деления с остатком к хешированию). Тогда можно надеяться, что количество холостых срабатываний есть 0(ra/g), поскольку вероятность того, что случайное число ts сравнимо с р по модулю q, равна 1/q. Стало быть, ожидаемое время работы алгоритма Рабина - Карпа есть

О(га) + 0(m(v + ra/g)),

где v - количество вхождений образца в текст. Если q гаг (то есть длина образца не превосходит выбранного значения q) и v = 0(1), то получается, что алгоритм работает за время О (га + гаг).

34.2.1. Упражнения

34.2-1

Сколько холостых срабатываний даст алгоритм Рабина-Карпа, если q = 11, Г = 3141592653589793 и Р = 26?

34.2-2 Обобщите алгоритм Рабина - Карпа на случай, когда в тексте надо искать одну из к данных подстрок.

34-2.3 Обобщите алгоритм Рабина - Карпа на случай, когда надо искать квадрат размером гаг X гаг в матрице размером га X га с