#include using namespace std; using ll = long long; // never fail to call build() !! // constructor() // add(string) // match(string) : [left, right], vec> in // right-order /// --- AhoCorasick Library {{{ /// struct AhoCorasick { struct Trie { unordered_map< char, Trie* > child; Trie* failure = nullptr; // vector< int > words; int words = 0; Trie* add(char c) { if(child.count(c)) { return child[c]; } else { return child[c] = new Trie; } } Trie* go(char c) { if(child.count(c)) { return child[c]; } else { if(failure == nullptr) { return this; } else { return failure->go(c); } } } }; Trie* top = new Trie; vector< string > dict; void add(string word) { Trie* now = top; for(size_t i = 0; i < word.size(); i++) { now = now->add(word[i]); } now->words++; // now->words.emplace_back(dict.size()); // dict.emplace_back(word); } void build() { queue< Trie* > q; q.emplace(top); while(q.size()) { Trie* now = q.front(); q.pop(); for(pair< char, Trie* > ch : now->child) { q.emplace(ch.second); Trie* failure = ch.second->failure = now == top ? top : now->failure->go(ch.first); /// only from failure!! // vector< int >& words = ch.second->words; // words.insert(end(words), begin(failure->words), end(failure->words)); ch.second->words += failure->words; } } } ll match(string s) { Trie* now = top; // vector< tuple< int, int, int > > res; ll res = 0; for(size_t i = 0; i < s.size(); i++) { now = now->go(s[i]); res += now->words; // for(int word : now->words) { // res.emplace_back(i - dict[word].size() + 1, i, word); // } } return res; } }; /// }}}--- /// int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); string s; cin >> s; int n; cin >> n; AhoCorasick ecasd; for(int i = 0; i < n; i++) { string t; cin >> t; ecasd.add(t); } ecasd.build(); cout << ecasd.match(s) << endl; return 0; }