#include using namespace std; struct TrieNode { int nxt[27]; int exist, accept; TrieNode() : exist(0), accept(0) { memset(nxt, -1, sizeof(nxt)); } }; struct Trie { vector< TrieNode > nodes; Trie() { nodes.push_back(TrieNode()); } virtual void direct_action(int node, int id) {} virtual void child_action(int node, int child, int id) {} void update_direct(int node, int id) { ++nodes[node].accept; direct_action(node, id); } void update_child(int node, int child, int id) { ++nodes[node].exist; child_action(node, child, id); } void add(const string &str, int str_index, int node_index, int id) { if(str_index == str.size()) { update_direct(node_index, id); } else { const int c = str[str_index] - 'A'; if(nodes[node_index].nxt[c] == -1) { nodes[node_index].nxt[c] = (int) nodes.size(); nodes.push_back(TrieNode()); } add(str, str_index + 1, nodes[node_index].nxt[c], id); update_child(node_index, nodes[node_index].nxt[c], id); } } void add(const string &str, int id) { add(str, 0, 0, id); } void add(const string &str) { add(str, nodes[0].exist); } int size() { return (nodes[0].exist); } int nodesize() { return ((int) nodes.size()); } }; struct Aho_Corasick : Trie { static const int FAIL = 26; vector< int > correct; Aho_Corasick() : Trie() {} void build() { correct.resize(nodes.size()); for(int i = 0; i < nodes.size(); i++) { correct[i] = nodes[i].accept; } queue< int > que; for(int i = 0; i < 27; i++) { if(~nodes[0].nxt[i]) { nodes[nodes[0].nxt[i]].nxt[FAIL] = 0; que.emplace(nodes[0].nxt[i]); } else { nodes[0].nxt[i] = 0; } } while(!que.empty()) { TrieNode &now = nodes[que.front()]; correct[que.front()] += correct[now.nxt[FAIL]]; que.pop(); for(int i = 0; i < 26; i++) { if(now.nxt[i] == -1) continue; int fail = now.nxt[FAIL]; while(nodes[fail].nxt[i] == -1) { fail = nodes[fail].nxt[FAIL]; } nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i]; que.emplace(now.nxt[i]); } } } int move(const string &str, int now = 0) { int ret = 0; for(auto &c : str) { while(nodes[now].nxt[c - 'A'] == -1) now = nodes[now].nxt[FAIL]; now = nodes[now].nxt[c - 'A']; ret += correct[now]; } return (ret); } }; int main() { string S; int M; cin >> S; cin >> M; Aho_Corasick aho; for(int i = 0; i < M; i++) { string T; cin >> T; aho.add(T); } aho.build(); cout << aho.move(S) << endl; }