Verify/ACAutomaton.test.cpp

View this file on GitHub
Last update: 2023-02-11 22:28:05+08:00
Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include "../String/ACAutomaton.hpp"

#include "../Template/Template.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]; }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << std::endl;
    // string s;
    // int m;
    // cin >> s >> m;

    // ACAutomaton<TrieNode> ac;
    // vector<int> pos(m + 1);
    // for (int i = 1; i <= m; i++) {
    //     string res;
    //     cin >> res;
    //     pos[i] = ac.add(res);
    // }
    // ac.BuildAC();

    // vector<int> val(ac.size());
    // vector<vector<int>> adj(ac.size());
    // for (int i = 0; i < ac.size(); i++) {
    //     if (i != ac.fail[i]) adj[ac.fail[i]].push_back(i);
    // }

    // int p = 0;
    // for (auto it : s) {
    //     p = ac.tr[p][it - 'A'];
    //     val[p]++;
    // }

    // function<void(int)> dfs = [&](int u) {
    //     for (auto v : adj[u]) {
    //         dfs(v);
    //         val[u] += val[v];
    //     }
    // };
    // dfs(0);

    // int ans = 0;

    // for (int i = 1; i <= m; i++) ans += val[pos[i]];
    // cout << ans << endl;

    return 0;
}

#line 1 "Verify/ACAutomaton.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#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;
    }
};
#line 4 "Verify/ACAutomaton.test.cpp"

#line 6 "Verify/ACAutomaton.test.cpp"

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]; }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << std::endl;
    // string s;
    // int m;
    // cin >> s >> m;

    // ACAutomaton<TrieNode> ac;
    // vector<int> pos(m + 1);
    // for (int i = 1; i <= m; i++) {
    //     string res;
    //     cin >> res;
    //     pos[i] = ac.add(res);
    // }
    // ac.BuildAC();

    // vector<int> val(ac.size());
    // vector<vector<int>> adj(ac.size());
    // for (int i = 0; i < ac.size(); i++) {
    //     if (i != ac.fail[i]) adj[ac.fail[i]].push_back(i);
    // }

    // int p = 0;
    // for (auto it : s) {
    //     p = ac.tr[p][it - 'A'];
    //     val[p]++;
    // }

    // function<void(int)> dfs = [&](int u) {
    //     for (auto v : adj[u]) {
    //         dfs(v);
    //         val[u] += val[v];
    //     }
    // };
    // dfs(0);

    // int ans = 0;

    // for (int i = 1; i <= m; i++) ans += val[pos[i]];
    // cout << ans << endl;

    return 0;
}