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

Модуль "Поиск" • урок 3 из 7 • ~10 минут

Как работает алгоритм Кнута-Морриса-Пратта

Секрет КМП заключается в том, что он перед началом поиска "изучает" сам искомый образец и строит для него префикс-функцию, сокращенно ПФ. Ячейка ПФ[i] относится не ко всему образцу, а только к его куску от начала и до символа с номером i включительно: в ней лежит длина наибольшего начала этого куска, которое совпадает с его концом и при этом короче самого куска.

Благодаря этому массиву, при ошибке совпадения КМП "знает", на сколько символов можно безопасно прыгнуть вперед, не пропустив возможное вхождение, что значительно экономит время. При этом указатель по самому тексту только увеличивается.

Разберем это на сквозном примере модуля: ищем образец ABABAC в тексте ABABADABABAC. Первые пять символов совпадают (ABABA), а на шестом вместо C стоит D. Буквы A и B в образце чередуются, и именно поэтому у него есть совпадающие начало и конец, которыми и пользуется префикс-функция. Наивный алгоритм отсюда откатился бы на одну позицию, а КМП смотрит в префикс-функцию и переставляет окно сразу на две. Три символа, которые при этом снова оказываются под образцом, новое окно берет готовыми - без единого сравнения.

Что записано в ячейке префикс-функции

Каждая ячейка отвечает за свой кусок образца, а не за образец целиком. Ниже - все шесть ячеек для ABABAC. Смысл числа: столько первых символов останутся верными, если окно поедет вперед. То есть в ячейке лежит не сдвиг, а то, сколько мы сохраняем.

Как эти числа найти перебором

Столбец "Начало = конец" показывает готовый ответ, но не показывает поиск. А искать приходится: формулы, по которой ПФ[i] считалось бы напрямую, не существует - есть только определение "самое длинное начало, совпадающее с концом", и нужное число из него добывается перебором длин. Честный способ такой: берем длину на единицу меньше самой подстроки и идем вниз, на каждой длине сравнивая начало с концом. Первое совпадение и есть ответ - раз шли от длинного к короткому, более длинного уже не будет.

Для подстроки ABABA (ячейка i = 4) перебор занимает две попытки:

Перебор дает верную таблицу, и на бумаге проверять себя удобно именно им. Но стоит он дорого: ячеек M, на каждую до M длин, а проверка одной длины - это сравнение двух кусков, снова до M символов. Для образца в тысячу символов это миллиарды операций, и выигрыш КМП пропал бы еще до начала поиска.

Как префикс-функция вычисляется по шагам

КМП получает ровно ту же таблицу, но перебора не ведет. Важно понимать: он вообще не сравнивает кусок с куском. Он сравнивает один символ с одним символом, ровно по одному сравнению на шаг, и переиспользует предыдущий ответ.

По образцу бегут два указателя: len - какой длины совпадение начала и конца уже набрано, и k - новый символ, который мы приписываем справа. Правило одно: чтобы совпадение выросло на единицу, новый символ P[k] должен совпасть с тем символом, который стоит сразу за уже совпавшим началом, то есть с P[len]. Удобно представлять себе две копии образца одна под другой, нижняя сдвинута вправо: нижняя копия - это начало, верхняя - конец.

Весь разбор образца ABABAC укладывается в семь сравнений:

Отдельно про откат в последних трех строках. При несовпадении len уменьшается не на единицу, а до ПФ[len-1] - до совпадения внутри совпадения. На шаге k = 5 набранным совпадением было ABA; следующий кандидат не AB, потому что ABABA на AB не заканчивается, а A - это и есть ПФ[2] = 1. Откат сразу перепрыгивает через заведомо невозможные варианты, и именно поэтому построение таблицы обходится без перебора.

Откуда берется величина сдвига

Теперь главное - как из таблицы получается сдвиг окна. Если совпало j символов и на следующем случилось расхождение, то

Ячейка берется с номером j-1, потому что это номер последнего совпавшего символа: совпало пять штук - последний из них имеет номер 4. Значение в ячейке говорит, сколько символов остается под образцом, а разность - на сколько позиций окно уезжает вперед.

Здесь легко споткнуться: в тренажере ниже два отката идут подряд и дают одинаковый сдвиг при разных числах в ячейках.

• совпало 5, ПФ[4] = 3, сдвиг 5 - 3 = 2;
• совпало 3, ПФ[2] = 1, сдвиг 3 - 1 = 2.

Противоречия нет: сдвиг - это разность, а не само значение ячейки. Растет ПФ - растет и j, а разность стоит на месте. Глубинная причина в том, что j - ПФ[j-1] это длина периода совпавшего куска. У ABABA период равен двум: пара AB повторяется. Наложиться сам на себя образец может только через целое число периодов, поэтому сдвиг и получается один и тот же.

Вторая классическая запись: таблица сдвигов d

Префикс-функция - не единственный способ записать то, что КМП успел узнать об образце. В исходной статье Кнута, Морриса и Пратта, в учебниках Н. Вирта и в англоязычных источниках ту же информацию хранят в таблице сдвигов d, и эта запись встречается не реже. Числа в ней те же самые, меняется нумерация; а у самой таблицы есть еще и усиленный вариант, который числа уже меняет.

Адресация по позиции несовпадения

Префикс-функцию нумеруют последним совпавшим символом - отсюда и j-1 в формуле сдвига. Таблицу d нумеруют иначе: позицией, на которой случилось расхождение. Это та же таблица, сдвинутая на одну ячейку вправо: d[j] = ПФ[j-1], а в освободившуюся нулевую ячейку кладут d[0] = -1. Формула сдвига при этом теряет минус единицу:

Для ABABAC обе записи выглядят так:

Числа те же самые, просто сдвинуты. Откат j := d[j] означает ровно то же, что и откат по префикс-функции: сравнение продолжается с символа P[d[j]], а окно уезжает вперед на j - d[j] позиций. Значение -1 в нулевой ячейке дает сдвиг на весь образец сразу: если не совпал уже первый символ, никакое частичное наложение невозможно.

Усиленная таблица: минус единица не только в нулевой ячейке

У записи d есть усиленный вариант, и в учебниках основным обычно является именно он. К требованию "начало совпадает с концом" добавляют условие P[d[j]] не равно P[j]. Смысл простой: мы попали в откат потому, что символ текста не совпал с P[j]. Если после отката под этот же символ текста встанет такая же буква образца, сравнение заведомо провалится - значит, его можно не делать, а откатиться сразу дальше. Если подходящего наложения не нашлось вовсе, в ячейку кладут -1.

Для ABABAC усиление меняет три ячейки из шести:

Разберем ячейку 2. Обычная таблица говорит d[2] = 0, то есть "сравни этот символ текста с P[0]". Но P[0] и P[2] - это одна и та же буква A, а мы уже знаем, что символ текста с A не совпал. Сравнение бессмысленно, поэтому усиленная таблица сразу отсылает дальше, к d[0], и записывает -1. По той же причине -1 попадает в ячейку 4. А ячейка 5 остается тройкой: там под несовпавший символ встает P[3] = B, а сорвалось сравнение на P[5] = C - буквы разные, значит сравнение имеет смысл.

Ячейка 3 меняется не из-за самой буквы, а по цепочке: обычная таблица посылает в P[1] = B, а сорвались мы на P[3] = B, поэтому усиленная перенаправляет туда же, куда ведет ячейка 1, то есть в 0.

На нашем примере выигрыш виден прямо в счетчике. Несовпадение D против C случается при j = 5, и дальше:

• обычная таблица откатывает j с 5 на 3, потом на 1, потом на 0: четыре сравнения с одним и тем же символом текста;
• усиленная откатывает j с 5 на 3, потом сразу на 0: три сравнения.

Весь поиск ABABAC в ABABADABABAC обходится в 15 сравнений по обычной таблице и в 14 по усиленной. Тренажер ниже и основной код на этой странице работают с обычной записью: она проще, а линейное время дает уже она.

Цикл поиска в этой записи

Запись через d позволяет свернуть поиск в один цикл, без развилки if / else:

while (j < M && i < N) {
    while (j >= 0 && s[i] != p[j]) {
        j = d[j];   // Откат по образцу, указатель по тексту стоит на месте
    }
    i++;            // А здесь оба указателя всегда шагают вперед
    j++;
}

Вся обработка несовпадений ушла во внутренний цикл, внешний только двигает указатели. Минус единица служит здесь ступенькой: если откат дошел до d[0] = -1, внутренний цикл заканчивается, а следующие i++ и j++ дают j = 0 и ставят начало образца под очередной символ текста. Без этой -1 пришлось бы отдельно разбирать случай "не совпал самый первый символ" - ровно тем if / else, который стоит в нашем основном коде ниже.

Реализация на языках C и C++

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

В коде массив по традиции называют lps - от longest proper prefix which is also suffix, то есть "наибольшее собственное начало, которое же является и концом". В математических текстах ту же функцию обозначают греческой буквой пи, отсюда встречающееся название "Pi-массив". Это все одно и то же, мы на странице зовем ее префикс-функцией; таблицей сдвигов принято называть запись d из раздела выше.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Функция предварительного анализа образа
void computeLPSArray(const char* pat, int M, int* lps) {
    int len = 0; // Длина предыдущего самого длинного префикса-суффикса
    lps[0] = 0;  // ПФ для строки длины 1 всегда 0
    int i = 1;

    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1]; // Откат по уже построенному массиву
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// Поиск алгоритмом КМП
void KMPSearch(const char* pat, const char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);

    int* lps = (int*)malloc(M * sizeof(int));
    computeLPSArray(pat, M, lps);

    int i = 0; // индекс для txt[]
    int j = 0; // индекс для pat[]
    
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }

        if (j == M) {
            printf("Найдено на индексе %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            // При несовпадении НЕ откатываем i
            if (j != 0) {
                j = lps[j - 1]; // Сдвигаем образец по массиву lps
            } else {
                i++;
            }
        }
    }
    free(lps);
}

А вот тот же алгоритм в записи через таблицу сдвигов - та самая версия, которую приводят Кнут, Моррис и Пратт в исходной статье, Н. Вирт в своих учебниках и англоязычная Википедия. Таблица здесь строится сразу усиленной, поиск свернут в один цикл, а отдельная проверка "не совпал первый символ" становится не нужна: ее заменяет значение -1.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Построение усиленной таблицы сдвигов: тот же КМП, примененный к самому образцу
void computeShiftTable(const char* p, int M, int* d) {
    int j = 0;
    int k = -1;
    d[0] = -1; // Несовпадение на первом символе: сдвиг сразу на весь образец

    while (j < M - 1) {
        while (k >= 0 && p[j] != p[k]) {
            k = d[k]; // Откат по уже построенной части таблицы
        }
        j++;
        k++;
        if (p[j] == p[k]) {
            d[j] = d[k]; // Усиление: под несовпавший символ не ставим такой же
        } else {
            d[j] = k;
        }
    }
}

// Поиск первого вхождения: указатель i по тексту никогда не идет назад
void KMPSearchShift(const char* p, const char* s) {
    int M = strlen(p);
    int N = strlen(s);
    int* d = (int*)malloc(M * sizeof(int));
    computeShiftTable(p, M, d);

    int i = 0; // Индекс в тексте
    int j = 0; // Индекс в образце
    while (j < M && i < N) {
        while (j >= 0 && s[i] != p[j]) {
            j = d[j]; // Окно едет вперед на j - d[j] позиций
        }
        i++;
        j++;
    }

    if (j == M) {
        printf("Найдено на индексе %d\n", i - M);
    }
    free(d);
}

Приведенный выше код на C собирается и компилятором C++ без единой правки - это проверено сборкой в режиме C++17. Но если вы пишете на C++, привычнее другая запись: std::string и std::vector вместо указателей и ручного выделения памяти. Здесь поиск сразу возвращает все вхождения, а не только первое.

#include <string>
#include <vector>

// Префикс-функция образца
std::vector<int> prefixFunction(const std::string& pat) {
    std::vector<int> lps(pat.size(), 0);
    int len = 0;                          // длина уже набранного совпадения
    for (std::size_t i = 1; i < pat.size(); ) {
        if (pat[i] == pat[static_cast<std::size_t>(len)]) {
            ++len;
            lps[i] = len;
            ++i;
        } else if (len != 0) {
            len = lps[len - 1];           // откат по уже построенной части
        } else {
            lps[i] = 0;
            ++i;
        }
    }
    return lps;
}

// Поиск всех вхождений: указатель по тексту не возвращается назад
std::vector<std::size_t> kmpSearch(const std::string& txt, const std::string& pat) {
    std::vector<std::size_t> found;
    if (pat.empty() || pat.size() > txt.size()) return found;

    const std::vector<int> lps = prefixFunction(pat);
    std::size_t j = 0;                    // сколько символов образца уже совпало
    for (std::size_t i = 0; i < txt.size(); ++i) {
        while (j > 0 && txt[i] != pat[j])
            j = static_cast<std::size_t>(lps[j - 1]);   // текст стоит, едет образец
        if (txt[i] == pat[j]) ++j;
        if (j == pat.size()) {
            found.push_back(i + 1 - pat.size());
            j = static_cast<std::size_t>(lps[j - 1]);
        }
    }
    return found;
}