#include using namespace std; using ll = long long; struct AhoCorasick { static const int CHAR_SIZE = 26; static const int MARGIN = 'A'; vector> nx; vector fail; vector> accept; vector correct; int node_count; AhoCorasick() { node_count = 1; nx.assign(1, {}); for (auto &a : nx[0]) a = -1; fail.assign(1, 0); accept.resize(1); } void add(const string &s, int id = -1) { int node = 0; for (char ch : s) { int c = ch - MARGIN; if (nx[node][c] == -1) { nx[node][c] = node_count++; nx.push_back({}); for (auto &a : nx.back()) a = -1; fail.push_back(0); accept.push_back({}); } node = nx[node][c]; } accept[node].push_back(id); } void build(bool heavy = true) { correct.assign(node_count, 0); for (int i = 0; i < node_count; i++) correct[i] = (int)accept[i].size(); queue q; for (int c = 0; c < CHAR_SIZE; c++) { int nxt = nx[0][c]; if (nxt != -1) { fail[nxt] = 0; q.push(nxt); } else { nx[0][c] = 0; } } while (!q.empty()) { int v = q.front(); q.pop(); int f = fail[v]; correct[v] += correct[f]; for (int c = 0; c < CHAR_SIZE; c++) { int u = nx[v][c]; if (u != -1) { fail[u] = nx[f][c]; if (heavy) { auto &A = accept[u]; auto &B = accept[fail[u]]; for (int id : B) A.push_back(id); sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end()); } q.push(u); } else { nx[v][c] = nx[f][c]; } } } } pair move(const char &c, int now = 0) const { now = nx[now][c - MARGIN]; return {correct[now], now}; } }; void solve() { string S; cin >> S; int M; cin >> M; AhoCorasick aho; for (int i = 0; i < M; i++) { string s; cin >> s; aho.add(s); } aho.build(); ll sum = 0; int now = 0; for (auto e : S) { auto [cnt, nxt] = aho.move(e, now); sum += cnt; now = nxt; } cout << sum << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); }