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

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

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово $\begin{displaymath} {\hbox{\tt X}}= {\hbox{\tt x[1]x[2]}}\ldots{\hbox{\tt x[n]}}\end{displaymath}$ и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел ${\hbox{\tt l[1]}}\ldots{\hbox{\tt l[n]}}$ , где $\begin{displaymath} {\hbox{\tt l[i]}} = \hbox{\rm длина слова }l({\hbox{\tt x[1]}}\ldots{\hbox{\tt x[i]}})\end{displaymath}$ (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[i]}}$ ,одновременно являющегося его концом.

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

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

$\scriptstyle{\blacktriangleright}$ 10.4.2. Описать алгоритм заполнения таблицы ${\hbox{\tt l[1]}}\ldots{\hbox{\tt l[n]}}$ .

Решение. Предположим, что первые i значений ${\hbox{\tt l[1]}}\ldots{\hbox{\tt l[i]}}$ уже найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1].

$\begin{displaymath} \newlength {\picwidth} \setlength {\picwidth}{.8\textwidt... ...\picwidth}}_Z$\hfill $\underbrace{\hspace*{.36\picwidth}}_Z$}}\end{displaymath}$

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

Получаем такой рецепт отыскания слова Z . Рассмотрим все начала слова ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[i]}}$ , являющиеся одновременно его концами. Из них выберем подходящие -- те, за которыми идет буква ${\hbox{\tt 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;`

$\scriptstyle{\blacktriangleright}$ 10.4.3. Доказать, что число действий в приведенном только что алгоритме не превосходит $C{\hbox{\tt n}}$ для некоторой константы C .

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

Более точно, можно записать неравенство $\begin{displaymath} {\hbox{\tt l[i+1]}} \leqslant{\hbox{\tt l[i]}} - \hbox{(число итераций на {\hbox{\tt i}}-м шаге)} + {\hbox{\tt 1}}\end{displaymath}$ или $\begin{displaymath} \hbox{(число итераций на {\hbox{\tt i}}-м шаге)}\leqslant{\hbox{\tt l[i]}}-{\hbox{\tt l[i+1]}} + {\hbox{\tt 1}}\end{displaymath}$ Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. $\scriptstyle\blacktriangleleft$

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

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

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

$\scriptstyle{\blacktriangleright}$ 10.4.5. Написать соответствующий алгоритм (проверяющий, является ли слово ${\hbox{\tt X}}={\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ подсловом слова ${\hbox{\tt Y}}={\hbox{\tt y[1]}}\ldots{\hbox{\tt y[m]}}$ ).

Решение. Сначала вычисляем таблицу ${\hbox{\tt l[1]}}\ldots{\hbox{\tt 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}`

pvv
1/8/1999