#include #define rep(i,a,b) for(int i=int(a);i> S; vector reptable[26]; int pre = 0; rep(i,1,S.size()){ if(S[i-1] != S[i]){ reptable[S[i-1] - 'A'].push_back(i - pre); pre = i; } } reptable[S.back() - 'A'].push_back(S.size() - pre); int M; cin >> M; ll cnt = 0; int table[10] = {}; rep(i,0,M){ string T; cin >> T; if(charsearch(T, T[0])){ int j = 0; rep(k,0,T.size()){ if(T[k] == T[j]){ table[k] = j++; }else{ table[k] = j; j = 0; } } int p = 0; rep(j,0,S.size()){ if(S[j] == T[p]){ p++; }else if(p == 0){ }else{ p = table[p]; j--; } if(p == T.size()){ cnt++; p = 0; } } }else{ for(int num:reptable[T[0] - 'A']){ cnt += max(0, (int)(num - T.size() + 1) ); } } } cout << cnt << endl; }