/** * @FileName a.cpp * @Author kanpurin * @Created 2022.09.21 01:58:39 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; struct Trie { struct Node { array ch; int cnt; int sub; Node () : cnt(0), sub(0) { fill(ch.begin(), ch.end(), -1); } }; vector nodes; Trie() : nodes(1) {} void insert(const string &s) { int t = 0; for (int i = 0; i < (int)s.size(); i++) { if (nodes[t].ch[s[i]-'A'] == -1) { nodes[t].ch[s[i]-'A'] = nodes.size(); nodes.push_back(Node()); } nodes[t].sub++; t = nodes[t].ch[s[i]-'A']; } nodes[t].sub++; nodes[t].cnt++; } }; struct AhoCorasick { Trie trie; vector failure; vector count; AhoCorasick() {} void insert(const string &s) { trie.insert(s); } void build() { for (int c = 0; c < 26; c++) { if (trie.nodes[0].ch[c] != -1) continue; trie.nodes[0].ch[c] = 0; } failure.resize(trie.nodes.size(),-1); count.resize(trie.nodes.size(),0); queue que; que.push(0); while(!que.empty()) { int v = que.front(); que.pop(); for (int c = 0; c < 26; c++) { int to = trie.nodes[v].ch[c]; if (to <= 0) continue; count[to] = trie.nodes[to].cnt; que.push(to); int now = v; while(now != 0 && trie.nodes[failure[now]].ch[c] == -1) { now = failure[v]; } failure[to] = (now==0?0:trie.nodes[failure[now]].ch[c]); count[to] += count[failure[to]]; } } } int move(int idx, int c) { if (trie.nodes[idx].ch[c] == -1) { return move(failure[idx],c); } else { return trie.nodes[idx].ch[c]; } } }; int main() { string s;cin >> s; int n;cin >> n; AhoCorasick aho; for (int i = 0; i < n; i++) { string t;cin >> t; aho.insert(t); } aho.build(); int now = 0; int ans = 0; for (int i = 0; i < s.size(); i++) { now = aho.move(now,s[i]-'A'); ans += aho.count[now]; } cout << ans << endl; return 0; }