#line 1 "A.cpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward(tail)...); } template void print(vector &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template void prisep(vector &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template void print(vector> &A){ for(auto &row: A) print(row); } #line 3 "Library/C++/string/AhoCorasick.hpp" using namespace std; struct AhoCorasick{ vector words; vector> children; vector> match; vector failure; AhoCorasick(){} void registe(string word){ words.push_back(word); } void build(){ children.assign(1, {}); match.assign(1, {}); for(int i = 0; i < words.size(); i++){ _register(i, words[i]); } failure.resize(children.size()); _create_failure(); } void _register(int i, string &word){ int k = 0; for(auto s:word){ if(children[k].count(s)) k = children[k][s]; else{ int le = children.size(); children[k][s] = le; children.push_back({}); match.push_back({}); k = le; } } match[k].push_back(i); } void _create_failure(){ queue que; for(auto tmp:children[0]) que.push(tmp.second); while(!que.empty()){ int k = que.front(); int b = failure[k]; que.pop(); for(auto tmp:children[k]){ int j = tmp.second; failure[j] = _next(b, tmp.first); match[j].insert(match[j].end(), match[failure[j]].begin(), match[failure[j]].end()); que.push(j); } } } int _next(int k, char s){ while(1){ if(children[k].count(s)) return children[k][s]; else if(k == 0) return 0; k = failure[k]; } } vector> search(string text){ int k = 0; int le = text.size(); vector> matched(le, vector()); for(int i = 0; i < le; i++){ k = _next(k, text[i]); for(auto m:match[k]){ matched[i - words[m].size() + 1].push_back(m); } } return matched; } }; #line 46 "A.cpp" void solve(){ string S; int n; cin >> S >> n; AhoCorasick ac; for(int i = 0; i < n; i++){ string T; cin >> T; ac.registe(T); } ac.build(); auto match = ac.search(S); int ls = S.size(); int ans = 0; for(int i = 0; i < match.size(); i++){ ans += match[i].size(); } print(ans); } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }