Алгоритм Ахо-Корасик

Материал из Олимпиадное программирование в УлГТУ
Версия от 00:22, 18 сентября 2020; Ctrlalt (обсуждение | вклад) (Новая страница: « class Trie { struct Vertex { bool isTerminal = false; map<char, Vertex> next; Vertex *sufLink = nullptr; map<char, Verte...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску
class Trie {
    struct Vertex {
        bool isTerminal = false;
        map<char, Vertex> next;
        Vertex *sufLink = nullptr;
        map<char, Vertex *> autLink;
    } root;

public:
    void add(const string &s) {
        Vertex *v = &root;
        for (const char &c : s)
            v = &v->next[c];
        v->isTerminal = true;
    }

    void build(int alphabetSize) {
        queue<Vertex *> q;
        root.sufLink = &root;
        q.push(&root);

        while (!q.empty()) {
            Vertex *v = q.front();
            q.pop();

            for (auto &[c, to] : v->next) {
                to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]);                
                q.push(&to);
            }

            for (char c = ' '; c < ' ' + alphabetSize; c++) {
                if (v->next.count(c))
                    v->autLink[c] = &v->next[c];
                else
                    v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
            }

            v->isTerminal |= v->sufLink->isTerminal;
        }
    }

    bool check(const string &s) {
        Vertex *v = &root;
        for (const char &c : s) {
            v = v->autLink[c];
            if (v->isTerminal)
                return true;
        }
        return false;
    }
};

Ссылки

Теория:

Код: