This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#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'; }