Доллар США
Евро
Алгоритм Кнута -Морриса -Пратта
Алгоритм Кнута - Морриса - Пратта (КМП) получает на вход слово
X = x[1]x[2]...x[n]
и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]..l[n], так что
l[i] = длина слова n(x[1]...x[i])
(функция n определена в предыдущем пункте). Словами: 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.
Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции n из предыдущего раздела. Вот что получается:
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
| | {начало оказалось неподходящим, применяем к нему n}
| | 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 длины m и запоминаем эти значения. Дальше мы помним только значение 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
| | {начало оказалось неподходящим, применяем к нему n}
| | 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;
| i := i+1;
end;
{если len=n, слово X встретилось; иначе мы дошли до конца
слова Y, так и не встретив X}
