Cherkay A. D.

Идеальный Баланс - твой выбор!

Рейтинг пользователей: / 7
ХудшийЛучший 




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


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


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}

 

 

 

 

You are here:

 

  Яндекс.Метрика

 

© Черкай А.Д., август, 2014