#include using namespace std; using ll = long long; template class Trie { public: Trie() : root(std::make_shared()) {} void insert(const std::string& s, int id) { insert(root, s, id, 0); } protected: struct Node; using node_ptr = std::shared_ptr; struct Node { std::vector ch; std::vector accept; int sz = 0; Node() : ch(Size) {} }; const node_ptr root; void insert(const node_ptr& t, const std::string& s, int id, int k) { ++t->sz; if (k == (int) s.size()) { t->accept.push_back(id); return; } int c = s[k] - Offset; if (!t->ch[c]) t->ch[c] = std::make_shared(); insert(t->ch[c], s, id, k + 1); } }; template class AhoCorasick : public Trie { using node_ptr = typename Trie::node_ptr; using Trie::root; static const int FAIL = Size; public: void build() { std::queue que; for (int i = 0; i <= Size; ++i) { if (root->ch[i]) { root->ch[i]->ch[FAIL] = root; que.push(root->ch[i]); } else { root->ch[i] = root; } } while (!que.empty()) { auto t = que.front(); que.pop(); for (int i = 0; i < Size; ++i) { if (!t->ch[i]) continue; auto fail = t->ch[FAIL]; while (!fail->ch[i]) fail = fail->ch[FAIL]; t->ch[i]->ch[FAIL] = fail->ch[i]; auto& u = t->ch[i]->accept; auto& v = fail->ch[i]->accept; std::vector accept; std::set_union(u.begin(), u.end(), v.begin(), v.end(), std::back_inserter(accept)); u = accept; que.push(t->ch[i]); } } } std::map match(const std::string& str) const { std::map ret; auto t = root; for (auto c : str) { while (!t->ch[c - Offset]) t = t->ch[FAIL]; t = t->ch[c - Offset]; for (auto& i : t->accept) ++ret[i]; } return ret; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); string S; cin >> S; int M; cin >> M; AhoCorasick<26, 'A'> aho; for (int i = 0; i < M; ++i) { string s; cin >> s; aho.insert(s, i); } aho.build(); auto ret = aho.match(S); ll ans = 0; for (int i = 0; i < M; ++i) ans += ret[i]; cout << ans << endl; }