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

Материал из Википедии — свободной энциклопедии

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм поиска образца (подстроки) в строке.

[править] Постановка задачи

Поставим следующую задачу: имеется образец и строка , и нужно определить индекс, начиная с которого строка содержится в строке . Если не содержится в — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).

[править] История возникновения

Этот алгоритм появился в результате тщательного анализа алгоритма грубой силы (англ. brute-force). Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования строки (алгоритм грубой силы ее просто выбрасывает).

Размер сдвига образца можно увеличить, одновременно запомнив части текста, совпадающие с образцом. Это позволит избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.

Рассмотрим сравнение строк на позиции , где образец сопоставляется с частью текста . Предположим, что первое несовпадение произошло между и , где . Тогда и .

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца сойдется с каким-нибудь суффиксом подслова текста . Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки .

Это приводит нас к следующему алгоритму: пусть — префикс-функция от строки . Тогда после сдвига мы можем возобновить сравнения с места и без потери возможного местонахождения образца. Таблица может быть вычислена за сравнений перед началом поиска.

[править] Пример практической реализации

Пусть ищется строка в строке . Построим строку , где символ — символ, не встречающийся ни в , ни в . Далее вычислим значения префикс-функции от строки и всех её префиксов. Теперь, если префикс-функция от префикса строки длины равна , где — длина , и , то в строке есть вхождение , начиная с позиции .

[править] Реализация алгоритма на языке Паскаль

Function pos (t,p : String) : integer;
 var F : array[0..length] of integer;
     k,i : integer;
 {t - подстрока;p - соотвественно строка}
 {length - сумма длин строки и подстроки }
 begin
  F[1] := 0;
  k := 0;
  For i := 2 to length(T) do
   begin
    While (k > 0) and (T[k+1] <> t[i]) do k := F[k];
    if T[k+1] = T[i] Then Inc(k);
    F[i] := k;
   end;
  k := 0;
  For i := 1 to length(P) do
   begin
    While (k > 0) and ( T[k+1] <> P[i]) do k := F[k];
    if T[k+1] = T[i] Then Inc(k);
    if k = length(T)
     Then
      Begin
       pos := i+length(t);
       {Здесь обрабатываются полученные данные после того как мы нашли подстроку,
 можно сделать результатом работы функции не только положение подстроки}
       Exit;
      End;
   end;
 end;

Возможно алгоритм немного неверный если найдете ошибки правьте.

[править] Ссылки

http://algolist.manual.ru/search/esearch/kmp.php

[править] См. также

• Алгоритм Бойера — Мура
• Дональд Кнут
• Алгоритм Ахо-Корасик