Алгоритм Кнута-Морриса-Пратта (Реализация на C#)

C#   4 июня 2012  Автор статьи:  

Алгоритм Кнута-Морриса-Пратта использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i больше одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, проверяется префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находится наибольший искомый префикс.Смысл префикс-функции в том, что можно отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcasdqtabc (следующий символ не совпал), то имеет смысл продолжать проверку уже с четвертого символа (первые три и так совпадут).
Реализация данного алгоритма на C#:

//Префикс-функция для КМП
public static int[] PrefFunc(string x)
{
//Инициализация массива-результата длиной X
int[] res = new int[x.Length];
int i = 0;
int j = -1;
res[0] = -1;
//Вычисление префикс-функции
while (i < x.Length - 1) { while ((j >= 0) && (x[j] != x[i]))
j = res[j];
i++;
j++;
if (x[i] == x[j])
res[i] = res[j];
else
res[i] = j;
}
return res;//Возвращение префикс-функции
}
//Функция поиска алгоритмом КМП
public static string KMP(string x, string s)
{
string nom = ""; //Объявление строки с номерами позиций
if (x.Length > s.Length) return nom; //Возвращает 0 поиск если образец больше исходной строки
//Вызов префикс-функции
int[] d = PrefFunc(x);
int i=0, j;
while (i < s.Length) { for (i = i, j = 0; (i < s.Length) && (j < x.Length); i++, j++) while ((j >= 0) && (x[j] != s[i]))
j = d[j];
if (j == x.Length)
nom = nom + Convert.ToString(i - j) + ", ";
}
if (nom != "")
{
nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
}
return nom; //Возвращение результата поиска
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++