#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 insert(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() { 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; } } } } conditional_t, long long> match(const string& s) { unordered_map pos_cnt; int pos = 0; for(const auto& c : s) { pos = next(pos, c - margin); ++pos_cnt[pos]; } conditional_t, long long> res{}; for(const auto& [key, val] : pos_cnt) { if constexpr(heavy) { for(const auto& x : st[key].idxs) res[x] += val; } else { res += 1ll * cnt[key] * val; } } return res; } int count(int pos) { return cnt[pos]; } }; int main(void) { string S; int M; cin >> S >> M; AhoCorasick<26, 'A', true> aho; for(int i = 0; i < M; i++) { string T; cin >> T; aho.insert(T, i); } aho.build(); unordered_map cnt = aho.match(S); int ans = 0; for(const auto& it : cnt) { ans += it.second; } cout << ans << '\n'; }