#include #define REP(i,n) for (long long i=0;i<(n);i++) using namespace std; typedef int string_size; struct Trie { int sz = 0; Trie* node[CHAR_MAX]; Trie* failure; vector accept; Trie() { for(string_size i=0; isz); for(string_size i=0; inode[c]) r->node[c] = new Trie; r = r->node[c]; } r->accept.push_back(dic_size-1); } }; // パターンマッチ, 辞書 <- 文字列(全ての部分列に分解) class AhoCorasick { private: Trie trie; void updateFailure() { Trie* root = ≜ queue que; for (char c = 0;c < CHAR_MAX;c++) { if (root->node[c]) { root->node[c]->failure = root; que.push(root->node[c]); } else root->node[c] = root; } while (!que.empty()) { Trie *t = que.front();que.pop(); for (char c = 0;c < CHAR_MAX;c++) { if ( t->node[c]) { que.push(t->node[c]); Trie *r = t->failure; while (!r->node[c]) r = r->failure; t->node[c]->failure = r->node[c]; t->node[c]->accept.insert(t->node[c]->accept.end(),r->node[c]->accept.begin(), r->node[c]->accept.end()); } } } } public: AhoCorasick(const vector &pattern) { for (int i = 0;i < pattern.size();i++) trie.insert(pattern[i]); updateFailure(); } // targetの部分列のうち,patternと一致するところをマッチング. // result[idx] := (辞書内の)idx番目の単語とマッチングする回数. // target := 一致させる単語 int match(string &target,vector &result) { Trie* v = ≜ int count = 0; for (string_size i = 0;i < target.size();i++) { char c = target[i]; while (! v->node[c]) v = v->failure; v = v->node[c]; for (string_size j = 0; j < v->accept.size(); ++j) result[v->accept[j]]++; count += (v->accept.size()); } return count; } }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); long M; string S; cin >> S >> M; vector C(M); REP(i,M) cin >> C[i]; AhoCorasick ac(C); vector result(M); cout << ac.match(S,result) << endl; }