Алгоритм Кнута - Морриса - Пратта
Реферат
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово
X=x[1]x[2]... x[n]
и просматривает его слева направо буква за буквой, заполняя при
этом массив натуральных чисел l[1]... l[n], где
l[i]=длина слова l(x[1]...х[i])
(функция l определена в предыдущем пункте). Словами: l[i] есть
длина наибольшего начала слова x[1]...x[i], одновременно являющегося его
концом.
Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения
того, является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # - специальная
буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B
тогда и только тогда, когда среди чисел в массиве l будет число, равное длине
слова A.
Описать алгоритм заполнения таблицы l[1]...l[n].
Решение. Предположим, что первые i значений l[1]...l[i] уже
найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить
l[i+1].
Другими словами, нас интересуют начала 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]. Из подходящих выберем самое
длинное. Приписав в его конец х[i+1], получим искомое слово Z. Теперь пора
воспользоваться сделанными нами приготовлениями и вспомнить, что все слова,
являющиеся одновременно началами и концами данного слова, можно получить
повторными применениями к нему функции l из предыдущего раздела.
Вот что получается:
i:=1; 1[1]:=0;
{таблица l[1]..l[i] заполнена правильно}
while i n do begin
len:= l[i]
{len - длина начала слова x[1]..x[i], которое является
его концом; все более длинные начала оказались
неподходящими}
while (x[len+1]х[i+1]) and (len>0) do begin
{начало не подходит, применяем к нему функцию l}
len:=l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1]=x[i+1] do begin
{х[1]..x[len] - самое длинное подходящее начало}
l[i+1]:=len+1;
end else begin
{подходящих нет}
l[i+1]:= 0;
end;
i:=i+1;
end;
Доказать, что число действий в приведенном только что алгоритме не
превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы
может потребовать многих итераций во внутреннем цикле. Однако каждая такая
итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется
заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина
l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не
может - иначе убывание не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l[i+1]