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

Алгоритм Кнута-Морриса-Пратта (КМП) — это эффективный алгоритм поиска подстроки в строке, разработанный для улучшения производительности по сравнению с наивными методами. Он работает за время O(n + m), где n — длина строки, а m — длина подстроки. Алгоритм использует предварительную обработку подстроки для создания префикс-функции, что позволяет избегать повторного сравнения символов.

Основная идея алгоритма

Алгоритм КМП использует префикс-функцию для подстроки. Префикс-функция определяет, на сколько символов можно сдвинуть подстроку, не теряя уже совпавшую часть. Это позволяет пропускать некоторые символы в строке, тем самым ускоряя процесс поиска.

Построение префикс-функции

Префикс-функция для строки p длины m — это массив pi, где pi[i] — это длина наибольшего собственного префикса подстроки p[0...i], который также является суффиксом этой подстроки.

Пример

Для строки p = "ababc" префикс-функция будет [0, 0, 1, 2, 0].

Этапы работы алгоритма

1. Построение префикс-функции для подстроки.
2. Поиск подстроки в строке с использованием префикс-функции.

Построение префикс-функции

#include <iostream>
#include <vector>
#include <string>
 
// Функция для вычисления префикс-функции
std::vector<int> computePrefixFunction(const std::string &pattern) {
    int m = pattern.length();
    std::vector<int> pi(m, 0);
    int k = 0;
 
    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[i] != pattern[k]) {
            k = pi[k - 1];
        }
        if (pattern[i] == pattern[k]) {
            k++;
        }
        pi[i] = k;
    }
 
    return pi;
}

Поиск подстроки

#include <iostream>
#include <vector>
#include <string>
 
// Функция для поиска подстроки в строке
std::vector<int> KMPSearch(const std::string &text, const std::string &pattern) {
    int n = text.length();
    int m = pattern.length();
    std::vector<int> pi = computePrefixFunction(pattern);
    std::vector<int> result;
    int k = 0;
 
    for (int i = 0; i < n; i++) {
        while (k > 0 && text[i] != pattern[k]) {
            k = pi[k - 1];
        }
        if (text[i] == pattern[k]) {
            k++;
        }
        if (k == m) {
            result.push_back(i - m + 1);
            k = pi[k - 1];
        }
    }
 
    return result;
}
 
int main() {
    std::string text = "ababcababcab";
    std::string pattern = "ababc";
    std::vector<int> result = KMPSearch(text, pattern);
 
    for (int pos : result) {
        std::cout << "Pattern found at index " << pos << std::endl;
    }
 
    return 0;
}

Объяснение

1. Построение префикс-функции:

   • Для каждой позиции i в подстроке pattern мы вычисляем длину наибольшего префикса, который также является суффиксом подстроки pattern[0...i].
   • Значение pi[i] используется для определения, сколько символов можно пропустить в случае несовпадения.

2. Поиск подстроки:

   • Проходим по строке text и подстроке pattern.
   • Для каждой позиции i в строке, если символы text[i] и pattern[k] совпадают, увеличиваем k.
   • Если символы не совпадают, используем значение pi[k-1] для определения новой позиции k.
   • Если достигли конца подстроки (т.е. k == m), это означает, что подстрока найдена в строке, и мы сохраняем позицию вхождения.

Преимущества алгоритма

• Эффективность: Алгоритм работает за время O(n + m), что значительно быстрее по сравнению с наивным методом O(n * m).
• Простота реализации: Несмотря на свою эффективность, алгоритм довольно прост для понимания и реализации.
• Универсальность: Алгоритм подходит для решения различных задач, связанных с поиском подстрок, например, в текстовых редакторах, биоинформатике и других областях.

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