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=2863" #include <iostream> #include <string> #include <vector> #include "../../modint/modint.hpp" #include "../../string/aho_corasick.hpp" using mint = ebi::modint1000000007; int main() { int n; std::cin >> n; ebi::aho_corasick<26, 'a'> aho; std::vector<std::string> s(n); for (int i = 0; i < n; i++) { std::cin >> s[i]; aho.add(s[i]); } aho.build(); std::string t; std::cin >> t; int m = t.size(); std::vector<mint> dp(m + 1, 0); dp[0] = 1; aho.query(t, [&](int i, int idx) -> void { dp[idx + 1] += dp[idx + 1 - int(s[i].size())]; }); std::cout << dp[m].val() << '\n'; }
#line 1 "test/aoj/aoj_2863.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863" #include <iostream> #include <string> #include <vector> #line 2 "modint/modint.hpp" #include <cassert> #line 5 "modint/modint.hpp" #line 2 "modint/base.hpp" #include <concepts> #line 5 "modint/base.hpp" #include <utility> namespace ebi { template <class T> concept Modint = requires(T a, T b) { a + b; a - b; a * b; a / b; a.inv(); a.val(); a.pow(std::declval<long long>()); T::mod(); }; template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) { long long x; os >> x; a = x; return os; } template <Modint mint> std::ostream &operator<<(std::ostream &os, const mint &a) { return os << a.val(); } } // namespace ebi #line 7 "modint/modint.hpp" namespace ebi { template <int m> struct static_modint { private: using modint = static_modint; public: static constexpr int mod() { return m; } static constexpr modint raw(int v) { modint x; x._v = v; return x; } constexpr static_modint() : _v(0) {} constexpr static_modint(long long v) { v %= (long long)umod(); if (v < 0) v += (long long)umod(); _v = (unsigned int)v; } constexpr unsigned int val() const { return _v; } constexpr unsigned int value() const { return val(); } constexpr modint &operator++() { _v++; if (_v == umod()) _v = 0; return *this; } constexpr modint &operator--() { if (_v == 0) _v = umod(); _v--; return *this; } constexpr modint operator++(int) { modint res = *this; ++*this; return res; } constexpr modint operator--(int) { modint res = *this; --*this; return res; } constexpr modint &operator+=(const modint &rhs) { _v += rhs._v; if (_v >= umod()) _v -= umod(); return *this; } constexpr modint &operator-=(const modint &rhs) { _v -= rhs._v; if (_v >= umod()) _v += umod(); return *this; } constexpr modint &operator*=(const modint &rhs) { unsigned long long x = _v; x *= rhs._v; _v = (unsigned int)(x % (unsigned long long)umod()); return *this; } constexpr modint &operator/=(const modint &rhs) { return *this = *this * rhs.inv(); } constexpr modint operator+() const { return *this; } constexpr modint operator-() const { return modint() - *this; } constexpr modint pow(long long n) const { assert(0 <= n); modint x = *this, res = 1; while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } constexpr modint inv() const { assert(_v); return pow(umod() - 2); } friend modint operator+(const modint &lhs, const modint &rhs) { return modint(lhs) += rhs; } friend modint operator-(const modint &lhs, const modint &rhs) { return modint(lhs) -= rhs; } friend modint operator*(const modint &lhs, const modint &rhs) { return modint(lhs) *= rhs; } friend modint operator/(const modint &lhs, const modint &rhs) { return modint(lhs) /= rhs; } friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.val() == rhs.val(); } friend bool operator!=(const modint &lhs, const modint &rhs) { return !(lhs == rhs); } private: unsigned int _v = 0; static constexpr unsigned int umod() { return m; } }; using modint998244353 = static_modint<998244353>; using modint1000000007 = static_modint<1000000007>; } // namespace ebi #line 2 "string/aho_corasick.hpp" #include <string.h> #include <algorithm> #line 7 "string/aho_corasick.hpp" #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 9 "test/aoj/aoj_2863.test.cpp" using mint = ebi::modint1000000007; int main() { int n; std::cin >> n; ebi::aho_corasick<26, 'a'> aho; std::vector<std::string> s(n); for (int i = 0; i < n; i++) { std::cin >> s[i]; aho.add(s[i]); } aho.build(); std::string t; std::cin >> t; int m = t.size(); std::vector<mint> dp(m + 1, 0); dp[0] = 1; aho.query(t, [&](int i, int idx) -> void { dp[idx + 1] += dp[idx + 1 - int(s[i].size())]; }); std::cout << dp[m].val() << '\n'; }