КМП-алгоритм

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

Постановка задачи

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

История возникновения

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

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

Рассмотрим сравнение строк на позиции $\displaystyle i$, где образец $\displaystyle x[ 0, m - 1 ]$ сопоставляется с частью текста $\displaystyle \displaystyle y[ i, i + m - 1 ]$. Предположим, что первое несовпадение произошло между $\displaystyle y[ i + j ]$ и $\displaystyle x[ j ]$, где $\displaystyle 1 < j < m$. Тогда $\displaystyle y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u$ и $\displaystyle a = y[ i + j ] \not= x[ j ] = b$.

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

Это приводит нас к следующему алгоритму: пусть $\displaystyle \rm{mp\_next}[ j ]$ — префикс-функция от строки $\displaystyle x[ 0, j - 1 ]$. Тогда после сдвига мы можем возобновить сравнения с места $\displaystyle y[ i + j ]$ и $\displaystyle x[ \rm{mp\_next}[ j ] ]$ без потери возможного местонахождения образца. Таблица $\displaystyle \rm{mp\_next}$ может быть вычислена за $\displaystyle O( m )$ сравнений перед началом поиска.

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

Пусть ищется строка $\displaystyle S_1$ в строке $\displaystyle S_2$. Построим строку $\displaystyle S=S_1\$S_2$, где символ $\displaystyle\$$ — символ, не встречающийся ни в $\displaystyle S_1$, ни в $\displaystyle S_2$. Далее вычислим значения префикс-функции от строки $\displaystyle S$ и всех её префиксов. Теперь, если префикс-функция от префикса строки $\displaystyle S$ длины $\displaystyle i$ равна $\displaystyle n$, где $\displaystyle n$ — длина $\displaystyle S_1$, и $\displaystyle i>n$, то в строке $\displaystyle S_2$ есть вхождение $\displaystyle S_1$, начиная с позиции $\displaystyle i-2n$.

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

 {t - подстрока; p - соотвественно строка}
Function Pos(t, p : String): Integer;
var
  F: array of Integer;
  k, i: integer;
begin
  SetLength(F, Length(t) + Length(p));
  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] = P[i] Then
      Inc(k);
    if k = Length(T) Then
    begin
      Result := i-length(t)+1;
      //Здесь обрабатываются полученные данные после того как мы нашли подстроку,
      //можно сделать результатом работы функции не только положение подстроки
      Break;
    end;
  end;
end;

Реализация алгоритма на языке C++

#include <string>
#include <vector>
 
using namespace std;
 
vector < int > KMP(string t, string p){
	vector < int > ch;
	string s = p + '$' + t;
	int n = (int) s.length();
	ch.resize(n);
	ch[0] = 0;
	for (int i = 1; i < n; i++){
		int t = ch[i - 1];
		while (t != 0 && s[i] != s[t])
			t = ch[t - 1];
		if (s[i] == s[t]) t++;
		ch[i] = t;
	}
	return ch;
}

Реализация алгоритма на языке Си

int  seek_substring_KMP  (char s[],   char q[])
	{ 
	int  i, j, N, M; 
	N = strlen(s); 
	M = strlen(q); 
	int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/ 
	/* Вычисление префикс-функции */ 
	i=0; 
	j=-1;
	d[0]=-1;
	while(i<M-1)
		{
		while((j>=0) && (q[j]!=q[i]))
			j = d[j];
		i++;
		j++;
		if(q[i]==q[j])
			d[i]=d[j];
		else
			d[i]= j;
		}
	/* поиск */
	for(i=0,j=0;(i<N)&&(j<M); i++,j++)
		while((j>=0)&&(q[j]!=s[i]))
			j=d[j];
	free (d);  /* освобождение памяти массива d */ 
	if (j==M)
		return i-j;
	else /* i==N */
		return -1;
	}

Реализация алгоритма на языке С#

public int FindSubstring(string input, string pattern)
{
	int n = input.Length;
	int m = pattern.Length;
	if (0 == n) throw new ArgumentException("String mustn't be empty", "input");
	if (0 == m) throw new ArgumentException("String mustn't be empty", "pattern");
 
	int[] d = GetPrefixFunction(pattern);
 
	int i, j;
	for (i = 0, j = 0; (i < n) && (j < m); i++, j++)
		while ((j >= 0) && (pattern[j] != input[i])) 
			j = d[j];
 
	if (j == m)
		return i - j;
	else 
		return -1;
}
 
private int[] GetPrefixFunction(string pattern)
{
	int length = pattern.Length;
	int[] result = new int[length];
 
	int i = 0;
	int j = -1;
	result[0] = -1;
	while (i < length - 1)
	{
		while ((j >= 0) && (pattern[j] != pattern[i]))
			j = result[j];
		i++;
		j++;
		if (pattern[i] == pattern[j])
			result[i] = result[j];
		else
			result[i] = j;
	}
	return result;
}

Ссылки

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

См. также

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