Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/Library

:heavy_check_mark: test/aoj/aoj_2873.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2873"

#include <iostream>

#include <string>

#include <vector>


#include "../../string/aho_corasick.hpp"


int main() {
    std::string s;
    int n;
    std::cin >> s >> n;
    ebi::aho_corasick<26, 'a'> ac;
    for (int i = 0; i < n; i++) {
        std::string p;
        std::cin >> p;
        ac.add(p);
    }
    ac.build();
    int now = 0;
    int ans = 0;
    for (auto c : s) {
        auto [x, y] = ac.move(c, now);
        if (x > 0) {
            ans++;
            now = 0;
        } else {
            now = y;
        }
    }
    std::cout << ans << '\n';
}
#line 1 "test/aoj/aoj_2873.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2873"

#include <iostream>

#include <string>

#include <vector>


#line 2 "string/aho_corasick.hpp"

#include <string.h>


#include <algorithm>

#include <cassert>

#include <map>

#include <queue>

#line 10 "string/aho_corasick.hpp"

#line 2 "string/trie.hpp"

#include <array>

#line 7 "string/trie.hpp"

namespace ebi {

template <int char_size, int margin> struct trie {
  private:
    struct trie_node {
        int common;
        std::array<int, char_size> nxt;
        std::vector<int> accept;
        trie_node() : common(0) {
            nxt.fill(-1);
        }
    };

  public:
    trie() {
        nodes.emplace_back(trie_node());
    }

    void add(const std::string &str) {
        int idx = 0;
        for (const auto &c : str) {
            int val = c - margin;
            assert(0 <= val && val < char_size);
            if (nodes[idx].nxt[val] < 0) {
                nodes[idx].nxt[val] = int(nodes.size());
                nodes.emplace_back(trie_node());
            }
            idx = nodes[idx].nxt[val];
            nodes[idx].common++;
        }
        nodes[idx].accept.emplace_back(nodes[0].common++);
    }

    template <class F>
    void query(const std::string &str, int start, F func) const {
        int idx = 0;
        for (int i = start; i < int(str.size()); ++i) {
            int val = str[i] - margin;
            assert(0 <= val && val < char_size);
            int nxt = nodes[idx].nxt[val];
            if (nxt < 0) {
                return;
            }
            idx = nxt;
            for (const auto id : nodes[idx].accept) {
                func(id);
            }
        }
        return;
    }

    bool search(const std::string &str, int start, bool prefix = false) const {
        int idx = 0;
        for (int i = start; i < int(str.size()); ++i) {
            int val = str[i] - margin;
            assert(0 <= val && val < char_size);
            int nxt = nodes[idx].nxt[val];
            if (nxt < 0) {
                return -1;
            }
            idx = nxt;
        }
        return prefix ? true : (nodes[idx].accept.size() > 0);
    }

    int size() const {
        return int(nodes.size());
    }

  protected:
    std::vector<trie_node> nodes;
};

}  // namespace ebi
#line 12 "string/aho_corasick.hpp"

namespace ebi {

template <int char_size, int margin>
struct aho_corasick : trie<char_size + 1, margin> {
  private:
    void move_nxt(int &now, int val) {
        assert(0 <= val && val < char_size);
        while (this->nodes[now].nxt[val] == -1)
            now = this->nodes[now].nxt[FAIL];
        now = this->nodes[now].nxt[val];
        return;
    }
    using trie<char_size + 1, margin>::trie;
    using trie<char_size + 1, margin>::nodes;

  public:
    void build() {
        correct.resize(this->size());
        for (int i = 0; i < this->size(); ++i) {
            correct[i] = int(this->nodes[i].accept.size());
        }
        std::queue<int> que;
        for (int i = 0; i <= char_size; ++i) {
            if (this->nodes[0].nxt[i] != -1) {
                this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
                que.push(this->nodes[0].nxt[i]);
            } else {
                this->nodes[0].nxt[i] = 0;
            }
        }
        while (!que.empty()) {
            int idx = que.front();
            que.pop();
            auto &now = this->nodes[idx];
            correct[idx] += correct[now.nxt[FAIL]];
            for (int i = 0; i < char_size; ++i) {
                if (now.nxt[i] == -1) continue;
                int fail = now.nxt[FAIL];
                while (this->nodes[fail].nxt[i] == -1)
                    fail = this->nodes[fail].nxt[FAIL];
                this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
                std::vector<int> &u = this->nodes[now.nxt[i]].accept;
                std::vector<int> &v =
                    this->nodes[this->nodes[fail].nxt[i]].accept;
                std::vector<int> accept;
                std::set_union(u.begin(), u.end(), v.begin(), v.end(),
                               std::back_inserter(accept));
                u = accept;
                que.push(now.nxt[i]);
            }
        }
    }

    std::map<int, int> match(const std::string &str, int now = 0) {
        std::map<int, int> map;
        for (const auto &c : str) {
            move_nxt(now, c - margin);
            for (const auto &a : this->nodes[now].accept) {
                map[a]++;
            }
        }
        return map;
    }

    template <class F> void query(const std::string &str, F func, int now = 0) {
        for (int i = 0; i < int(str.size()); ++i) {
            move_nxt(now, str[i] - margin);
            for (const auto &a : this->nodes[now].accept) {
                func(a, i);
            }
        }
        return;
    }

    std::pair<int, int> move(const char &c, int now) {
        int sum = 0;
        move_nxt(now, c - margin);
        sum += correct[now];
        return {sum, now};
    }

  private:
    const int FAIL = char_size;
    std::vector<int> correct;
};

}  // namespace ebi

#line 8 "test/aoj/aoj_2873.test.cpp"

int main() {
    std::string s;
    int n;
    std::cin >> s >> n;
    ebi::aho_corasick<26, 'a'> ac;
    for (int i = 0; i < n; i++) {
        std::string p;
        std::cin >> p;
        ac.add(p);
    }
    ac.build();
    int now = 0;
    int ans = 0;
    for (auto c : s) {
        auto [x, y] = ac.move(c, now);
        if (x > 0) {
            ans++;
            now = 0;
        } else {
            now = y;
        }
    }
    std::cout << ans << '\n';
}
Back to top page