#line 2 "library/KowerKoint/base.hpp" #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include using namespace std; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define END(...) { print(__VA_ARGS__); return; } using VI = vector; using VVI = vector; using VVVI = vector; using ll = long long; using VL = vector; using VVL = vector; using VVVL = vector; using VD = vector; using VVD = vector; using VVVD = vector; using VS = vector; using VVS = vector; using VVVS = vector; using VC = vector; using VVC = vector; using VVVC = vector; using P = pair; using VP = vector

; using VVP = vector; using VVVP = vector; using LP = pair; using VLP = vector; using VVLP = vector; using VVVLP = vector; template using PQ = priority_queue; template using GPQ = priority_queue, greater>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; void print() { cout << '\n'; } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } #ifdef ONLINE_JUDGE template void dbg(const Args &... args) {} #else void dbg() { cerr << '\n'; } template void dbg(const T &t) { cerr << t << '\n'; } template void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } #endif template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template vector> split(typename vector::const_iterator begin, typename vector::const_iterator end, T val) { vector> res; vector cur; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(val); } res.push_back(cur); return res; } vector split(typename string::const_iterator begin, typename string::const_iterator end, char val) { vector res; string cur = ""; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(val); } res.push_back(cur); return res; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template pair> compress(const vector &a) { int n = a.size(); vector x; REP(i, n) x.push_back(a[i]); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin(); return make_pair(res, x); } template pair, vector> factorial(int n) { vector res(n+1), rev(n+1); res[0] = 1; REP(i, n) res[i+1] = res[i] * (i+1); rev[n] = 1 / res[n]; for(int i = n; i > 0; i--) { rev[i-1] = rev[i] * i; } return make_pair(res, rev); } #line 2 "library/KowerKoint/test/yukicoder-430/main.cpp" /* #include */ /* using namespace atcoder; */ /* #include "KowerKoint/expansion/ac-library/all.hpp" */ #line 2 "library/KowerKoint/string.hpp" #line 4 "library/KowerKoint/string.hpp" template vector kmp_table(It begin, It end) { int m = end - begin; vector table(m); int j = 0; FOR(i, 1, m) { while(j > 0 && *(begin+i) != *(begin+j)) j = table[j-1]; if(*(begin+i) == *(begin+j)) table[i] = ++j; } return table; } template vector kmp_find(It s_begin, It s_end, It t_begin, It t_end, vector& table) { int n = s_end - s_begin; int m = t_end - t_begin; vector res; int j = 0; REP(i, n) { while(j > 0 && *(s_begin+i) != *(t_begin+j)) j = table[j-1]; if(*(s_begin+i) == *(t_begin+j)) { if(++j == m) { res.push_back(i - (m-1)); j = table[m-1]; } } } return res; } template struct Trie { struct Node { T c; unordered_map nxt; Node* failure; vector fullmatch_keyword_id; vector suffixmatch_keyword_id; Node(T _c): c(_c) { nxt.reserve(30); } }; Node* root; int keyword_id = 0; Trie() { root = new Node(root_char); } template void add(It begin, It end, int keyword_id_) { Node* cursor = root; for(It it = begin; it != end; it++) { if(!cursor->nxt.count(*it)) cursor->nxt[*it] = new Node(*it); cursor = cursor->nxt[*it]; } cursor->fullmatch_keyword_id.push_back(keyword_id_); } void add(const string& str, int keyword_id_=-1) { add(ALL(str), keyword_id_ == -1? keyword_id++ : keyword_id_); } void build_failure() { queue que; for(auto [c, to] : root->nxt) { to->failure = root; for(int x : to->fullmatch_keyword_id) { to->suffixmatch_keyword_id.push_back(x); } que.push(to); } while(!que.empty()) { Node* from = que.front(); que.pop(); for(auto [c, to] : from->nxt) { Node* cursor = from->failure; while(cursor != root && !cursor->nxt.count(c)) cursor = cursor->failure; if(cursor->nxt.count(c)) to->failure = cursor->nxt[c]; else to->failure = root; for(int x : to->fullmatch_keyword_id) { to->suffixmatch_keyword_id.push_back(x); } for(int x : to->failure->suffixmatch_keyword_id) { to->suffixmatch_keyword_id.push_back(x); } que.push(to); } } } template void aho_corasick(It begin, It end, function&)>& f) { Node* cursor = root; for(It it = begin; it != end; it++) { while(cursor != root && !cursor->nxt.count(*it)) cursor = cursor->failure; if(cursor->nxt.count(*it)) { cursor = cursor->nxt[*it]; f(cursor->suffixmatch_keyword_id); } } } template ll aho_corasick(It begin, It end) { ll res = 0; function&)> f = [&](vector& v) { res += v.size(); }; aho_corasick(begin, end, f); return res; } void aho_corasick(string &s, function&)>& f) { aho_corasick(ALL(s), f); } ll aho_corasick(string &s) { return aho_corasick(ALL(s)); } }; #line 7 "library/KowerKoint/test/yukicoder-430/main.cpp" void solve(){ string s; cin >> s; int m; cin >> m; ll ans = 0; Trie trie; REP(i, m) { string c; cin >> c; trie.add(c); } trie.build_failure(); print(trie.aho_corasick(s)); } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { // Fasterize input/output script ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(100); // scanf/printf user should delete this fasterize input/output script int t = 1; //cin >> t; // comment out if solving multi testcase for(int testCase = 1;testCase <= t;++testCase){ solve(); } return 0; }