#include using namespace std; #define rep(i,a,b) for(int i=a;i > V; int find(string s) { int cur = 0; for(char it : s) if ((cur = V[cur][it + 1]) == 0) return -1; return cur; } void create(vector S) { // 0 is for backtrack V.clear(); V.push_back(vector(NUMC + 1)); sort(S.begin(), S.end()); for(string it: S) { int cur = 0; for(char c: it) { if (V[cur][c + 1] == 0) V.push_back(vector(NUMC + 1)), V[cur][c + 1] = V.size() - 1; cur = V[cur][c + 1]; } } } }; class ACmatch_num { public: Trie t; vector acc; int ma; void create(vector S) { int i; ma = S.size(); t.create(S); acc.clear(); acc.resize(t.V.size()); rep(i, 0, S.size()) acc[t.find(S[i])]++; queue Q; rep(i, 0, NUMC) if (t.V[0][i + 1]) t.V[t.V[0][i + 1]][0] = 0, Q.push(t.V[0][i + 1]); while (!Q.empty()) { int k = Q.front(); Q.pop(); rep(i, 0, NUMC) if (t.V[k][i + 1]) { Q.push(t.V[k][i + 1]); int pre = t.V[k][0]; while (pre && t.V[pre][i + 1] == 0) pre = t.V[pre][0]; t.V[t.V[k][i + 1]][0] = t.V[pre][i + 1]; acc[t.V[k][i + 1]] += acc[t.V[pre][i + 1]]; } } } int match(string S) { int R = 0; int cur = 0; for(char it : S) { while (cur && t.V[cur][it + 1] == 0) cur = t.V[cur][0]; cur = t.V[cur][it + 1]; R += acc[cur]; } return R; } }; //----------------------------------------------------------------- string S; int M; vector C; ACmatch_num ac; //----------------------------------------------------------------- int main() { cin >> S >> M; rep(i, 0, M) { string s; cin >> s; rep(j, 0, s.length()) s[j] -= 'A'; C.push_back(s); } ac.create(C); cout << ac.match(S) << endl; }