#include using namespace std; struct AhoCorasick { vector> succ; vector fail, accept; char from, to; AhoCorasick(char from = 'a', char to = 'z') : from(from), to(to), succ(1, vector(to - from + 1)), accept(1) { } void add(string s) { int curr = 0; for (char c : s) { c -= from; if (succ[curr][c] == 0) { succ[curr][c] = succ.size(); succ.push_back(vector(to - from + 1)); accept.push_back(0); } curr = succ[curr][c]; } accept[curr]++; } void build() { queue q; for (int c = 0; c <= to - from; c++) { if (succ[0][c] != 0) { q.push(succ[0][c]); } } fail.resize(succ.size()); while (!q.empty()) { int curr = q.front(); q.pop(); for (int c = 0; c <= to - from; c++) { int next = succ[curr][c]; if (next != 0) { q.push(next); fail[next] = succ[fail[curr]][c]; } else { succ[curr][c] = succ[fail[curr]][c]; } } accept[curr] += accept[fail[curr]]; } } }; int main() { string S; cin >> S; int m; cin >> m; AhoCorasick aho('A', 'Z'); for (int ii = 0; ii < m; ii++) { string c; cin >> c; aho.add(c); } aho.build(); int v = 0; int ans = 0; for (char ch : S) { v = aho.succ[v][ch - 'A']; ans += aho.accept[v]; } cout << ans << endl; }