#include using namespace std; using ll = long long; // #define int ll using PII = pair; #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() 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 vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a,Ts... ts) { return vector(ts...))>(a,make_v(ts...)); } template typename enable_if::value==0>::type fill_v(T &t, const V &v) { t=v; } template typename enable_if::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template ostream &operator <<(ostream& out,const pair& a){ out<<'('< istream& operator >> (istream& is, vector& vec){ for(T& x: vec) is >> x; return is; } template ostream &operator <<(ostream& out,const vector& a){ out<<'['; for(T i: a) {out< struct AhoCorasick { // trie木のnode struct node { int fail; vector next; vector matched; node() : fail(-1), next(types, -1) {} }; // node の集合 vector nodes; // 辞書の種類数, trie木の根 int sz, root; // 文字と数字の対応付けをする関数 using F = function; F trans; // 初期化 AhoCorasick() {} AhoCorasick(vector pattern, F f = [](char c){return c-'a';}) : sz(pattern.size()), root(0) { nodes.resize(1); trans = f; build(pattern); } // vectorを結合 vector unite(const vector &a, const vector &b) { vector ret; set_union(ALL(a), ALL(b), back_inserter(ret)); return ret; } // 文字列集合patternからtrie木っぽいオートマトンを作成 void build(vector pattern) { int now; nodes[root].fail = root; REP(i, pattern.size()) { now = root; for(const auto &c: pattern[i]) { if(nodes[now].next[trans(c)] == -1) { nodes.push_back(node()); nodes[now].next[trans(c)] = nodes.size() - 1; } now = nodes[now].next[trans(c)]; } nodes[now].matched.push_back(i); } queue que; REP(i, types) { if(nodes[root].next[i] == -1) { nodes[root].next[i] = root; } else { nodes[nodes[root].next[i]].fail = root; que.push(nodes[root].next[i]); } } while(que.size()) { now = que.front(); que.pop(); REP(i, types) { if(nodes[now].next[i] != -1) { int nxt = nodes[now].fail; while(nodes[nxt].next[i] == -1) nxt = nodes[nxt].fail; int nxt_tmp = nodes[now].next[i]; nodes[nxt_tmp].fail = nodes[nxt].next[i]; nodes[nxt_tmp].matched = unite(nodes[nxt_tmp].matched, nodes[nodes[nxt].next[i]].matched); que.push(nxt_tmp); } } } } // 一文字ずつ照合していく int next(int p, const char c) { while(nodes[p].next[trans(c)] == -1) p = nodes[p].fail; return nodes[p].next[trans(c)]; } // 文字列s中に辞書と一致する部分列がどれだけあるか vector match(const string s) { vector res(sz); int now = root; for(auto c : s) { now = next(now, c); for(auto i : nodes[now].matched) res[i]++; } return res; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(false); int m; string s; cin >> s >> m; vector c(m); cin >> c; auto trans = [&](char c){ return c-'A'; }; AhoCorasick<26> aho(c, trans); auto ret = aho.match(s); int ans = 0; for(auto i: ret) ans += i; cout << ans << endl; return 0; }