НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Алгоритм Кнута-Морриса-Пратта

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

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

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово

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].

[pic]

Другими словами, нас интересуют начала 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;