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

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

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году[2].

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

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

Идея[править | править вики-текст]

Алгоритм Ахо-Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.

Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.

если haystack[i] = needle[state]
  то state = state + 1
  иначе state = побочный_переход(state, haystack[i])

Легко заметить, что суффиксные ссылки алгоритма Ахо-Корасик представляют собой префикс-функцию искомого шаблона.

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

Рассмотрим сравнение строк на позиции \displaystyle i, где образец \displaystyle S[ 0, m - 1 ] сопоставляется с частью текста \displaystyle \displaystyle T[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между \displaystyle \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 S сойдется с каким-нибудь суффиксом (конечные символы) текста \displaystyle P. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки \displaystyle S для индекса \displaystyle j.

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

Алгоритм на 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 (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; //Возвращение результата поиска
}

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

Примечания[править | править вики-текст]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
  2. Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). «Fast pattern matching in strings». SIAM Journal on Computing 6 (2): 323–350. DOI:10.1137/0206024.

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