10.4. Алгоритм Кнута - Морриса - Пратта

Алгоритм Кнута - Морриса - Пратта (КМП) получает на вход слово
X = x[1]x[2]...x[n]

и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]..l[n], где
l[i] = длина слова l(x[1]...x[i])

(функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]..x[i], одновременно являющегося его концом.

10.4.1. Какое отношение все это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?

Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.

10.4.2. Описать алгоритм заполнения таблицы l[1]..l[n].

Решение. Предположим, что первые i значений l[1]..l[i] уже найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1].
1 i i+1
--------------------------------------------------------
| уже прочитанная часть x | |
--------------------------------------------------------
\-----------Z-----------/ \------------Z------------/

Другими словами, нас интересуют начала Z слова x[1]..x[i+1], одновременно являющиеся его концами - из них нам надо выбрать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова Z' приписыванием буквы x[i+1]. Слово Z' является началом и концом слова x[1]..x[i]. Однако не любое слово, являющееся началом и концом слова x[1]..x[i], годится - надо, чтобы за ним следовала буква x[i+1].

Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x[1]..x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное. Приписав в его конец x[i+1], получим искомое слово Z.

Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела. Вот что получается:
i:=1; l[1]:= 0;
{таблица l[1]..l[i] заполнена правильно}
while i <> n do begin
| len := l[i]
| {len - длина начала слова x[1]..x[i], которое является
| его концом; все более длинные начала оказались
| неподходящими}
| while (x[len+1] <> x[i+1]) and (len > 0) do begin
| | {начало не подходит, применяем к нему функцию l}
| | len := l[len];
| end;
| {нашли подходящее или убедились в отсутствии}
| if x[len+1] = x[i+1] do begin
| | {x[1]..x[len] - самое длинное подходящее начало}
| | l[i+1] := len+1;
| end else begin
| | {подходящих нет}
| | l[i+1] := 0;
| end;
| i := i+1;
end;

10.4.3. Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.

Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.

Более точно, можно записать неравенство
l[i+1] <= l[i] - (число итераций на i-м шаге) + 1

или
(число итераций на i-м шаге) <= l[i] - l[i+1] + 1
Остаётся сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций.

10.4.4. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C*(n+m), и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное).

Решение. Применяем алгоритм КМП к слову A#B. При этом вычисление значений l[1],...,l[n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы l[1]..l[n], нам для вычислений ничего не нужно.

На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.

10.4.5. Написать соответствующий алгоритм (проверяющий, является ли слово X=x[1]..x[n] подсловом слова Y=y[1]..y[m]).

Решение. Сначала вычисляем таблицу l[1]..l[n] как раньше. Затем пишем такую программу:
j:=0; len:=0;
{len - длина максимального начала слова X, одновременно
являющегося концом слова y[1]..j[j]}
while (len <> n) and (j <> m) do begin
| while (x[len+1] <> y[j+1]) and (len > 0) do begin
| | {начало не подходит, применяем к нему функцию l}
| | len := l[len];
| end;
| {нашли подходящее или убедились в отсутствии}
| if x[len+1] = y[j+1] do begin
| | {x[1]..x[len] - самое длинное подходящее начало}
| | len := len+1;
| end else begin
| | {подходящих нет}
| | len := 0;
| end;
| j := j+1;
end;
{если len=n, слово X встретилось; иначе мы дошли до конца
слова Y, так и не встретив X}

Другие записи

10.06.2016. 10.5. Алгоритм Бойера - Мура
  Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея…
10.06.2016. 10.6. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образем длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли…
10.06.2016. 10.7. Более сложные образцы и автоматы
  Мы можем искать не конкретно слово, а подслова заданного вида. Например, можно искать слова вида a?b, где вместо ? может стоять любая буква (иными словами, нас интересует буква b на расстоянии…