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

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

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово \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]}}$,годится -- над