String/ACAutomaton.hpp

View this file on GitHub
Last update: 2023-02-11 22:28:05+08:00
Include: #include "String/ACAutomaton.hpp"

Depends on

Verified with

Verify/ACAutomaton.test.cpp

Code

#pragma once

#include "Trie.hpp"

template <class Node>
struct ACAutomaton : public trie<Node> {
    std::vector<int> fail;
    ACAutomaton(){};

    void BuildAC() {
        fail.resize(this->tr.size());
        std::queue<int> Q;
        for (int i = 0; i < 26; i++)
            if (this->tr[0][i]) Q.push(this->tr[0][i]);
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i = 0; i < 26; i++) {
                if (this->tr[u][i])
                    fail[this->tr[u][i]] = this->tr[fail[u]][i],
                    Q.push(this->tr[u][i]);
                else
                    this->tr[u][i] = this->tr[fail[u]][i];
            }
        }
        return;
    }
};

#line 2 "String/ACAutomaton.hpp"

#line 2 "Template/Template.hpp"

#include <bits/stdc++.h>

using i64 = std::int64_t;
#line 3 "String/Trie.hpp"

// struct TrieNode {
//     TrieNode() { id = 0, dep = 0, nxt = std::array<int, 26>(); };
//     TrieNode(int _id, int _dep) : id(_id), dep(_dep) {}
//     int id;
//     int dep;
//     std::array<int, 26> nxt = {};
//     int &operator[](const int x) { return this->nxt[x]; }
// };
template <class Node>
struct trie {
    std::vector<Node> tr;
    trie() { tr.push_back(Node()); };

    int add(const std::string &s) {
        int n = s.size();
        int p = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            if (!tr[p][c]) {
                tr[p][c] = tr.size();
                tr.emplace_back(tr[p][c], tr[p].dep + 1);
            }
            p = tr[p][c];
        }
        return p;
    }

    int size() const { return tr.size(); }
};
#line 4 "String/ACAutomaton.hpp"

template <class Node>
struct ACAutomaton : public trie<Node> {
    std::vector<int> fail;
    ACAutomaton(){};

    void BuildAC() {
        fail.resize(this->tr.size());
        std::queue<int> Q;
        for (int i = 0; i < 26; i++)
            if (this->tr[0][i]) Q.push(this->tr[0][i]);
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i = 0; i < 26; i++) {
                if (this->tr[u][i])
                    fail[this->tr[u][i]] = this->tr[fail[u]][i],
                    Q.push(this->tr[u][i]);
                else
                    this->tr[u][i] = this->tr[fail[u]][i];
            }
        }
        return;
    }
};