#include using namespace std; using ll = long long; using P = pair; #define rep(i, a, b) for(ll i = a; i < b; ++i) #define rrep(i, a, b) for(ll i = a; i >= b; --i) constexpr ll inf = 4e18; struct SetupIO { SetupIO() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(30); } } setup_io; template struct Trie { struct Node { array nxt; vector idxs; int idx; int count; char key; Node(char c) : idx(-1), count(0), key(c) { fill(nxt.begin(), nxt.end(), -1); } }; vector st; Trie(char c = '$') { st.emplace_back(c); } inline int& next(int i, int j) { return st[i].nxt[j]; } void add(const string& s, int x) { int pos = 0; for(int i = 0; i < (int)s.size(); ++i) { ++st[pos].count; int k = s[i] - margin; if(~next(pos, k)) { pos = next(pos, k); continue; } int npos = st.size(); next(pos, k) = npos; st.emplace_back(s[i]); pos = npos; } ++st[pos].count; st[pos].idx = x; st[pos].idxs.emplace_back(x); } int find(const string& s) { int pos = 0; for(int i = 0; i < (int)s.size(); ++i) { int k = s[i] - margin; if(next(pos, k) < 0) return -1; pos = next(pos, k); } return pos; } int move(int pos, char c) { assert(pos < (int)st.size()); return pos < 0 ? -1 : next(pos, c - margin); } int size() const { return st.size(); } int idx(int pos) { return pos < 0 ? -1 : st[pos].idx; } int count(int pos) { return pos < 0 ? 0 : st[pos].count; } vector idxs(int pos) { return pos < 0 ? vector() : st[pos].idxs; } }; template struct AhoCorasick : Trie { using TRIE = Trie; using TRIE::next; using TRIE::st; using TRIE::TRIE; vector cnt; void build(bool heavy = true) { int n = (int)st.size(); cnt.resize(n); for(int i = 0; i < n; ++i) { if(heavy) sort(st[i].idxs.begin(), st[i].idxs.end()); cnt[i] = (int)st[i].idxs.size(); } queue que; for(int i = 0; i < (int)X; ++i) { if(~next(0, i)) { next(next(0, i), X) = 0; que.emplace(next(0, i)); } else { next(0, i) = 0; } } while(!que.empty()) { auto& x = st[que.front()]; int fail = x.nxt[X]; cnt[que.front()] += cnt[fail]; que.pop(); for(int i = 0; i < (int)X; ++i) { int& nx = x.nxt[i]; if(nx < 0) { nx = next(fail, i); continue; } que.emplace(nx); next(nx, X) = next(fail, i); if(heavy) { auto& idx = st[nx].idxs; auto& idy = st[next(fail, i)].idxs; vector idz; set_union(idx.begin(), idx.end(), idy.begin(), idy.end(), back_inserter(idz)); idx = idz; } } } } vector match(const string& s, bool heavy = true) { vector res(heavy ? TRIE::size() : 1); int pos = 0; for(const auto& c : s) { pos = next(pos, c - margin); if(heavy) { for(const auto& x : st[pos].idxs) ++res[x]; } else { res[0] += cnt[pos]; } } return res; } int count(int pos) { return cnt[pos]; } }; int main(void) { string S; int M; cin >> S >> M; AhoCorasick<26, 'A'> aho; for(int i = 0; i < M; i++) { string T; cin >> T; aho.add(T, i); } aho.build(); vector cnt = aho.match(S); int ans = 0; rep(i, 0, (int)cnt.size()) { ans += cnt[i]; } cout << ans << '\n'; }