#include using i64 = long long; namespace Trie { template struct Node { Node *next[alphabet_size]; unsigned exist; std::vector accept; Node() : next(), exist(0) {} }; template class NodePool { unsigned pool_size; unsigned pos; std::allocator> alc; Node *pool; public: NodePool(unsigned size) : pool_size(size), pos(0), pool(alc.allocate(pool_size)) {} ~NodePool() { for (unsigned i = 0; i < pos; i++) pool[pos - 1 - i].~Node(); alc.deallocate(pool, pool_size); } auto alloc() { return new(pool + pos++) Node(); } }; template struct Trie { NodePool pool; Node *root; void add_impl(const std::string &str, unsigned id) { auto node = root; for (unsigned c : str) { c -= margin; if (node->next[c] == nullptr) { node->next[c] = pool.alloc(); } node->exist++; node = node->next[c]; } node->accept.push_back(id); } // maximum size of node pool explicit Trie(unsigned max_pool_size) : pool(max_pool_size), root(pool.alloc()) {} void add(const std::string &str) { add_impl(str, root->exist); } }; template struct AhoCorasick : Trie { using TrieF = Trie; using NodeF = Node; using TrieF::root; static constexpr unsigned failure = alphabet_size; static constexpr unsigned prefix = failure + 1; AhoCorasick(unsigned max_pool_size) : TrieF(max_pool_size) {} // build pattern matching automaton from trie void build() { std::deque q { root }; root->next[failure] = root; while (!q.empty()) { auto node = q.front(); q.pop_front(); for (unsigned c = 0; c < alphabet_size; c++) { if (node->next[c] == nullptr) continue; q.push_back(node->next[c]); auto fail_next = node->next[failure]; while (fail_next->next[c] == nullptr && fail_next != root) { fail_next = fail_next->next[failure]; } node->next[c]->next[failure] = fail_next->next[c] && fail_next != node ? fail_next->next[c] : root; auto t = node->next[c]->next[failure]; node->next[c]->next[prefix] = t->accept.size() ? t : t->next[prefix]; } } } auto transition(NodeF *node, unsigned c) { c -= margin; while (node->next[c] == nullptr && node != root) { node = node->next[failure]; } return node->next[c] ? node->next[c] : node; } auto match(const std::string &str) { std::vector ret(root->exist); auto node = root; for (unsigned c : str) { node = transition(node, c); auto t = node; while (t && t != root) { for (auto w : t->accept) ret[w]++; t = t->next[prefix]; } } return ret; } // F: (id: unsigned, r: unsigned) -> void // [r - length, r) template void match_apply(const std::string &str, const F &f) { auto node = root; for (std::size_t i = 0; i < str.size(); i++) { node = transition(node, str[i]); auto t = node; while (t && t != root) { for (auto w : t->accept) f(w, i + 1); t = t->next[prefix]; } } } }; } int main() { std::string s; int m; std::cin >> s >> m; std::vector c(m); Trie::AhoCorasick<26, 'A'> ac(50000); for (auto &e : c) { std::cin >> e; ac.add(e); } i64 ret = 0; auto f = [&](auto id, auto r) { ret++; }; ac.build(); ac.match_apply(s, f); std::cout << ret << std::endl; return 0; }