очевидно, o{Ti) = 0 и q = 0; в обоих случаях второе утверждение выполнено. Наконец, если второе утверждение верно для некоторого г < п, то, очевидно, первое утверждение верно для г+1. Это завершает индукцию и доказательство.

Упражнения

34.4-1

Найдите префикс-функцию для строки ababbabbababbababbabb. 34.4-2

Укажите верхнюю оценку на размер множества 7Г*[д] (как функцию от q) и покажите, что ваша оценка неулучшаема. 34.4-3

Как можно найти все вхождения образца Р в текст Г, зная префикс-функцию строки РТ (конкатенация Р и Г)? 34.4-4

Покажите, что в алгоритме KMP-Matcher можно в строке 7 (но не в строке 12) заменить тт на тт, где функция тт определена так:

тгМ

0,если 7г[д] = 0;

тг[7г[д]], если n[q] ф 0 и P[n[q] + 1] = P[q + 1]; тг[д], если тг[д] ф 0 и P[n[q] + 1] ф P[q + 1].

Почему можно сказать, что такая модификация алгоритма KMP-Matcher является его усовершенствованием? 34.4-5

Укажите работающий за линейное время алгоритм, выясняющий, является ли данная строка Г циклической перестановкой строки Т (например, строки arc и саг получаются одна из другой циклической перестановкой).

34.4-6

Разработайте эффективный алгоритм, вычисляющий функцию перехода 8 для конечного автомата, ищущего подстроку Р[1..т] в строке символов алфавита £. Ваш алгоритм должен работать за время 0(m\T<\). (Указание. Докажите, что S(q,a) = S(Tr[q],a), если q = m или P[q + 1] ф а.)

34.5. Алгоритм Бойера - Мура

Если образец Р длинный, а алфавит £ достаточно велик, то наиболее эффективным алгоритмом поиска подстрок является, видимо, следующий алгоритм, изобретенный Бойером (Robert S. Boyer) и Муром (J. Strother Moore):

Boyer-Moore-Matcher(Т,Р,\Sigma)

1п \gets length[Т]

2m \gets length[Р]

3\lambda \gets Compute-Last-Occurrence-Function(P,m,\Sigma)

4\gamma \gets Compute-Good-Svrff ix-Function(P,m)

5s \gets 0

6while s \leqslant n-m

7do j \gets m

8while j>0 and P[j]=T[s+j]

9do j \gets j-1

10if j=0

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

12s \gets s+\gamma[0]

13else s \gets s+\max(\gamma[j],j-\lambda[T[s+j]])

Если не обращать внимания на загадочные А и 7, этот алгоритм очень похож на простейший алгоритм поиска подстрок. В самом деле, если мы закомментируем строки 3-4 и заменим строки 12-13 на

12s \gets s+1

13else s \gets s+1,

то получится в точности простейший алгоритм разд. 34.1, с той единственной разницей, что сравнение Р[1..то] и T[s+l..s + то] идет справа налево, а не слева направо.

Алгоритм Бойера - Мура вносит в простейший алгоритм со сравнением справа налево два усовершенствования, называемые «эвристикой стоп-символа» и «эвристикой безопасного суффикса» (см. рис. 34.11). Эти эвристики позволяют не рассматривать некоторые (на практике - весьма многие) значения сдвига s. Обе эвристики действуют независимо и используются одновременно. Если при проверке сдвига s обнаруживается, что подстрока T[s + l..s + то] не совпадает с образцом, то каждая из эвристик указывает значение, на которое можно увеличить s, не опасаясь пропустить допустимый сдвиг (это j - X[T[s + j]] для эвристики стоп-символа и для эвристики безопасного суффикса); алгоритм Бойера - Мура выбирает из двух сдвигов больший.

34.5.1. Эвристика стоп-символа

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

Рис. 34.11, занимающий целую страницу. Переводы текстов на рисунке: bad character - стоп-символ, good suffix - безопасный суффикс.

Подпись:

Рис. 34.11. Эвристики Бойера - Мура (мы ищем в тексте подстроку reminiscence), (а) При сравнении сдвинутого на s образца с текстом (справа налево) выяснилось, что две крайние правые буквы совпадают (они образуют «безопасный суффикс» се), а третья справа буква в образце - не такая, как в тексте (в тексте на этом месте стоит «стоп-символ» i: на нем сравнение строк обрывается), (б) Эвристика стоп-символа предлагает сдвинуть образец вправо на такое расстояние, чтобы стоп-символ в тексте оказался напротив крайнего правого вхождения этого символа в образец. В нашем случае это означает сдвиг на 4 позиции. Если стоп-символа в образце вообще нет, то образец надо полностью задвинуть за стоп-символ текста; если стоп-символ в образце встречается правее стоп-символа в тексте, то эвристика стоп-символа ничего полезного не предлагает (даёт отрицательный сдвиг, который будет проигнорирован алгоритмом), (в) Эвристика безопасного суффикса предлагает сдвинуть образец вправо настолько, чтобы ближайшее (если смотреть справа налево) вхождение безопасного суффикса в образец оказалось напротив безопасного суффикса в тексте. В нашем примере это означает сдвиг на 3 позиции. Алгоритм Бойера - Мура выбирает больший из двух рекомендуемых сдвигов (в нашем случае - сдвиг на 4).