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

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

Текущая версия (не проверялась)

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

Содержание

1 Постановка задачи
2 История возникновения
3 Описание алгоритма и оценка времени работы
4 Пример практической реализации
5 Реализация алгоритма на языке Паскаль
6 Реализация алгоритма на языке C++
7 Реализация алгоритма на языке Си
8 Реализация алгоритма на языке С#
9 Реализация алгоритма на языке Java
10 Ссылки
11 См. также

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

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

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

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

[править] Описание алгоритма и оценка времени работы

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

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

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

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

Пусть ищется строка $\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;
}

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

void KMP (char[] haystack, char[] needle) {
	int m = needle.length;
	int n = haystack.length;
	int[] pf = new int[m];
	pf[0] = -1;
	//Вычисление префикс-функции
	for(int i = 1; i <= m; i ++) {
		pf[i] = pf[i - 1] + 1;
		while(pf[i] > 0 && needle[i - 1] != needle[pf[i] - 1])
			pf[i] = pf[pf[i] - 1] + 1;
	}
	//Сопоставление образца
	for(int i = 0, j = 0; i < n; i ++) {
		while(j > 0 && needle[j] != haystack[i])
			j = pf[j];
		if(needle[j] == haystack[i])
			j ++;
		if(j == m) {
			//Образец обнаружен на сдвиге i - m + 1
			//Ищем следующее вхождение образца
			j = pf[j];
		}
	}
}

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

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

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

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

Содержание

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

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

[править] Описание алгоритма и оценка времени работы

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

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

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

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

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

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

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

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

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках