#include #include #include #define rep(n, i) for (int i = 0; i < n; i++) using namespace std; template struct Aho { static constexpr int size = end - start + 1; struct node { bool term; int fail; int in; int nxt[size]; int move[size]; }; vector nodes = {node{}}; vector ids; vector cnt; void add(const string& s) { int cur = 0; for (auto c: s) { if (nodes[cur].nxt[c - start] == 0) { nodes.push_back(node{}); nodes[cur].nxt[c - start] = nodes.size() - 1; } cur = nodes[cur].nxt[c - start]; } nodes[cur].term = true; ids.push_back(cur); } void init() { deque que; rep(size, i) { int nxt = nodes[0].nxt[i]; if (nxt != 0) { nodes[0].move[i] = nxt; nodes[0].in++; nodes[nxt].fail = 0; rep(size, j) { nodes[nxt].move[j] = nodes[0].nxt[j]; } que.push_back(nxt); } } while (!que.empty()) { int u = que.front(); que.pop_front(); rep(size, i) { int nxt = nodes[u].nxt[i]; if (nxt != 0) { nodes[u].move[i] = nxt; int fail = nodes[nodes[u].fail].move[i]; nodes[nxt].fail = fail; nodes[fail].in++; rep(size, j) { nodes[nxt].move[j] = nodes[fail].move[j]; } que.push_back(nxt); } } } } void search(const string& s) { cnt = vector(nodes.size(), 0); int cur = 0; for (auto c: s) { cur = nodes[cur].move[c - start]; cnt[cur]++; } vector que; vector tin(nodes.size()); rep(nodes.size(), i) { tin[i] = nodes[i].in; if (tin[i] == 0) { que.push_back(i); } } while (!que.empty()) { int u = que.back(); que.pop_back(); int nxt = nodes[u].fail; cnt[nxt] += cnt[u]; tin[nxt]--; if (tin[nxt] == 0) { que.push_back(nxt); } } } int count(int id) { return cnt[ids[id]]; } }; int main() { string s; int m; cin >> s >> m; Aho<'A', 'Z'> aho; rep(m, i) { string c; cin >> c; aho.add(c); } aho.init(); aho.search(s); int ans = 0; rep(m, i) { ans += aho.count(i); } cout << ans << endl; }