#include using namespace std; using ll = long long; #define int ll using PII = pair; template using V = vector; template using VV = vector>; template using VVV = vector>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll INF = (1LL<<60); const int MOD = 1000000007; template T &chmin(T &a, const T &b) { return a = min(a, b); } template T &chmax(T &a, const T &b) { return a = max(a, b); } template bool IN(T a, T b, T x) { return a<=x&&x T ceil(T a, T b) { return a/b + !!(a%b); } template ostream &operator <<(ostream& out,const pair& a){ out<<'('< ostream &operator <<(ostream& out,const vector& a){ out<<'['; REP(i, a.size()) {out< struct AhoCorasick { // trie木のnode struct node { node *fail; V next; V matched; node() : fail(nullptr), next(types, nullptr) {} }; // 辞書のサイズ int sz; // trie木の根 node *root; // vectorを結合 V unite(const V &a, const V &b) { V ret; set_union(ALL(a), ALL(b), back_inserter(ret)); return ret; } // 文字と数字の対応付けをする関数 function trans; // 初期化 AhoCorasick() {} AhoCorasick(V pattern, function f = [](char c){return c-'a';}) { trans = f; build(pattern); } // 文字列集合patternからtrie木っぽいオートマトンを作成 void build(V pattern) { sz = pattern.size(), root = new node; node *now; root->fail = root; REP(i, sz) { now = root; for(const auto &c: pattern[i]) { if(now->next[trans(c)] == nullptr) { now->next[trans(c)] = new node; } now = now->next[trans(c)]; } now->matched.PB(i); } queue que; REP(i, types) { if(root->next[i] == nullptr) { root->next[i] = root; } else { root->next[i]->fail = root; que.push(root->next[i]); } } while(que.size()) { now = que.front(); que.pop(); REP(i, types) { if(now->next[i] != nullptr) { node *nxt = now->fail; while(!nxt->next[i]) nxt = nxt->fail; now->next[i]->fail = nxt->next[i]; now->next[i]->matched = unite(now->next[i]->matched, nxt->next[i]->matched); que.push(now->next[i]); } } } } // 一文字ずつ照合していく node* next(node* p, const char c) { while(p->next[trans(c)] == nullptr) p = p->fail; return p->next[trans(c)]; } // 文字列s中に辞書と一致する部分列がどれだけあるか V match(const string s) { V res(sz); node *now = root; for(auto c : s) { now = next(now, c); for(auto i : now->matched) res[i]++; } return res; } }; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); string s; cin >> s; int n; cin >> n; V v(n); REP(i, n) cin >> v[i]; AhoCorasick<26> aho(v, [&](char c){ return c-'A'; }); auto ret = aho.match(s); int ans = 0; for(int i: ret) ans += i; cout << ans << endl; return 0; }