(иными словами, Р[г] = Р[т + 1 - i] и 7r[t] - максимальное и < t, для которого Ри □ Р().

Пусть участок X строки Р заканчивается в позиции к (то есть является суффиксов строки Рк) и равен P[j + 1..то]. Длины обоих равных участков равны то - j, и легко понять, что эти участки (в перевёрнутом виде) будут суффиксом и префиксом строки Р{, где / = (то - к) + (то - j) (здесь (то - к) - расстояние от конца участка X до конца образца, (то - j) - длина участка). Поэтому 7г[/] то - j. Докажем, что на самом деле имеет место равенство

В самом деле, если бы более длинный участок X, начинающийся в той же позиции, что и X, был бы суффиксом образца, то некоторый его суффикс совпадал бы с P\j-\-l..m] и потому X не был бы самым правым участком строки Р, совпадающим с P[j + 1..то],

Равенство (34.8) можно переписать как j = то - 7г[/]; кроме того, из него следует, что к = то - / + тт[1]. поэтому можно окончательно переписать нашу формулу для так:

= то -тах({7г[то]}и{ то -/+7г[/] : 1 < I т и j = т - тг[1]}) = min({ то - тг[то] } U { / - тг[1] :1/tohj = to - тг[/] }) (34.9)

(опять-таки, второе множество может оказаться пустым).

Теперь можно выписать псевдокод для функции, вычисляющей

7-

Comput e-Good-Suffix-Funct ion(P,m)

1\pi \gets Compute-Prefix-Function(P,m)

2P \gets обращение строки P

3\pi \gets Compute-Prefix-Function(P,m)

4for j \gets 0 to m

5do \gamma[j] \gets m-\pi[m]

6for 1 \gets 1 to m

7do j \gets m - \pi[l]

8if \gamma[j] > 1 - \pi[l]

9then \gamma[j] \gets 1 - \pi[l]

10return \gamma

Процедура Compute-Good-Suffix-Function проводит вычисления в точности по формуле (34.9). Её время работы есть О (то).

Время работы алгоритма Бойера - Мура в худшем случае есть 0((п - то + 1)то + £), поскольку на исполнение Compute-Last-Occurrence-Function уходит время 0(то + £), на Compute-Good-Suffix-Function уходит О(то), и в худшем случае алгоритм Бойера - Мура (как и алгоритм Рабина - Карпа) потратит время О (то) на проверку каждого априори возможного сдвига. На практике, однако, именно алгоритм Бойера-Мура часто оказывается наиболее эффективным.

7г[/] = ТО - j.

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

34.5-1

Вычислите функции А и 7 для строки Р = 0101101201. 34.5-2

Покажите на примерах, что эвристики стоп-символа и эвристика безопасного суффикса, действуя вместе, могут дать большой выигрыш по сравнению с использованием только эвристики безопасного суффикса.

34-5.3*

На практике вместо функции 7 часто используют усовершенствованную функцию у, определенную так:

y[j] = то - max{ к : 0 к < то, P[j + l..m] ~ Р

n(k-m + j>0=> P[j] ф Р[к - то + j]) }

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

Задачи

34-1 Алгоритм поиска, учитывающий повторения в образце Через у1 будем далее обозначать г-кратную конкатенацию строки у с собой (например, (ab)3 = ababab). Будем говорить, что строка х £ У* имеет коэффициент повторения (has repetition factor) г, если х = уг, где г > 0 и у £ У*. Через р(х) обозначим наибольший из коэффициентов повторения строки х.

(а)Разработайте эффективный алгоритм, находящий р(Р{) для данной строки Р и для всех г = 1, 2,..., то. Оцените время работы вашего алгоритма.

(б)Для строки Р[1..то] положим р*(Р) = maxi8m р(Р{). Пусть У = 2 и строка Р выбирается случайным образом. Покажите, что математическое ожидание р*(Р) ограничено сверху константой, не зависящей от то.

(в)Покажите, что приведенная ниже программа находит все вхождения образца Р в текст Г за время 0(р*(Р)п + то).

Repetition-Matcher(Р,Т)

1m \gets length[Р]

2п \gets length[Т]

3к \gets l+\rho~*(P)

4q \gets 0

5s \gets 0

6 while s \leqslant n-m

7do if T[s+q+l]=P[q+l]

8then q \gets q+1

9if q=m

10then print

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

11if q=m или T[s+q+l]\ne P[q+1]

12then s \gets s+\max(l, \lceil q/k \rceil)

13q \gets 0

Этот алгоритм предложили Галил и Сейферас. Развивая эти идеи, они получили алгоритм для поиска подстрок, работающий за линейное время и использующий всего 0(1) памяти помимо требуемой для хранения Р и Т.

34-2 Параллельный алгоритм поиска

Обсудим, как можно использовать параллельный компьютер для поиска подстрок. Пусть для данного образца Р у нас есть конечный автомат М, предназначенный для поиска Р в тексте. Пусть Q - множество его состояний, а (р - функция, которая ставит в соответствие каждому слову состояние автомата М после чтения этого слова. Пусть Т[1..га] - текст, в котором мы ищем образец Р, тогда нам необходимо найти <~р(Т{) для всех г. Мы будем действовать как в разделе 30.1.2.

Для всякой строки х обозначим через 8x(q) состояние автомата М, в которое он придёт, если поместить его в состояние q и подать на вход строку х. (Таким образом, 8Х есть функция из Q в Q.)

(а)Покажите, что 8у о 8Х = 8ху (в левой части стоит композиция отображений).

(б)Покажите, что операция о ассоциативна.

(в)Покажите, что таблица значений функции 8ху может быть вычислена на CREW PRAM за время 0(1) исходя из таблиц значений 8Х и 8у. Оцените необходимое для этого число процессоров в зависимости от \Q\.

(г)Покажите, что <~р(Т{) = 8тг(уо), где до - исходное состояние.

(д)Покажите, что на CREW PRAM все вхождения образца Р в текст Г длины га можно найти за время О (lgra) (считайте, что образец Р задан в виде соответствующего конечного автомата).

34.6. Замечания

Связь задачи о поиске подстрок с конечными автоматами обсуждается у Ахо, Хопкрофта и Ульмана [4]. Алгоритм Кнута - Морриса - Пратта был независимо изобретен Кнутом и Моррисом, с одной стороны, и Праттом - с другой; в результате они опубли-