Построение автомата для поиска подстроки в строке

Автомат для поиска подстроки в строке, также известный как конечный автомат для поиска подстроки, представляет собой эффективный способ нахождения всех вхождений заданной подстроки в строку. Этот метод основывается на построении автоматного графа, где состояния соответствуют префиксам подстроки, а переходы управляются символами строки. Этот подход обеспечивает время выполнения O(n), где n — длина строки.

Основные понятия

Состояние (State): Представляет текущий префикс подстроки, который совпал с частью строки.
Переход (Transition): Определяет переход от одного состояния к другому при чтении определенного символа.
Начальное состояние (Start State): Состояние, с которого начинается процесс поиска.
Конечное состояние (Accepting State): Состояние, которое обозначает, что подстрока найдена.

Пример

Для подстроки pattern = "ababc" строим следующий автомат:

Состояние 0: начальное состояние.
Состояние 1: символ ‘a’ найден.
Состояние 2: префикс “ab” найден.
Состояние 3: префикс “aba” найден.
Состояние 4: префикс “abab” найден.
Состояние 5: подстрока “ababc” найдена (конечное состояние).

Построение автомата

Алгоритм

Инициализация:
- Создаем матрицу переходов для каждого символа алфавита и каждого состояния.
- Инициализируем начальное состояние (0).
Заполнение таблицы переходов:
- Для каждого состояния и символа определяем следующее состояние.
- Используем префикс-функцию для определения переходов, аналогично алгоритму Кнута-Морриса-Пратта.

Построение автомата на C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
 
class Automaton {
public:
    Automaton(const std::string &pattern) : pattern(pattern) {
        buildAutomaton();
    }
 
    std::vector<int> search(const std::string &text) {
        std::vector<int> result;
        int state = 0;
        for (int i = 0; i < text.size(); i++) {
            state = transition(state, text[i]);
            if (state == pattern.size()) {
                result.push_back(i - pattern.size() + 1);
            }
        }
        return result;
    }
 
private:
    std::string pattern;
    std::vector<std::vector<int>> automaton;
 
    void buildAutomaton() {
        int m = pattern.size();
        automaton.resize(m + 1, std::vector<int>(256, 0));
        for (int i = 0; i <= m; i++) {
            for (char c = 0; c < 256; c++) {
                automaton[i][c] = nextState(i, c);
            }
        }
    }
 
    int nextState(int state, char c) {
        if (state < pattern.size() && c == pattern[state]) {
            return state + 1;
        }
        for (int ns = state; ns > 0; ns--) {
            if (pattern[ns - 1] == c) {
                bool matched = true;
                for (int j = 0; j < ns - 1; j++) {
                    if (pattern[j] != pattern[state - ns + 1 + j]) {
                        matched = false;
                        break;
                    }
                }
                if (matched) {
                    return ns;
                }
            }
        }
        return 0;
    }
 
    int transition(int state, char c) {
        return automaton[state][c];
    }
};
 
int main() {
    std::string text = "ababcababcab";
    std::string pattern = "ababc";
    Automaton automaton(pattern);
    std::vector<int> result = automaton.search(text);
 
    for (int pos : result) {
        std::cout << "Pattern found at index " << pos << std::endl;
    }
 
    return 0;
}

Объяснение

Инициализация:
- Создаем матрицу automaton, где automaton[state][c] содержит следующее состояние для состояния state при чтении символа c.
Заполнение таблицы переходов:
- Функция nextState определяет следующее состояние для каждого состояния и символа.
- Если символ совпадает с ожидаемым символом подстроки, переходим в следующее состояние.
- В противном случае, используем префикс-функцию для определения перехода.
Поиск подстроки:
- Проходим по строке, используя матрицу переходов для определения следующего состояния.
- Если достигли конечного состояния, добавляем индекс начала подстроки в список результатов.

Преимущества и недостатки

Преимущества:

Эффективность: Время выполнения поиска — O(n), где n — длина строки.
Предсказуемость времени выполнения: Независимо от содержания строки, алгоритм всегда выполняется за линейное время.

Недостатки:

Потребление памяти: В худшем случае, матрица переходов может потреблять много памяти, особенно если алфавит большой.
Сложность реализации: Построение автомата может быть сложным для понимания и реализации.

Заключение

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

m4lvx

Explorer