#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)< pii; typedef vector vi; typedef vector vll; struct RollingHash{ static const int C = 31, C2 = 29, P = 1000000007, P2 = 1000000009; int _n; vector pw, pw2, hs, hs2; RollingHash(){} RollingHash(const string &st) :_n((int)st.size()), pw(_n+1),pw2(_n+1),hs(_n+1),hs2(_n+1) { pw[0] = pw2[0] = 1; rep(i, _n){ pw[i+1] = (pw[i]*C)%P; pw2[i+1] = (pw2[i]*C2)%P2; hs[i+1] = (C*hs[i]+st[i])%P; hs2[i+1] = (C2*hs2[i]+st[i])%P2; } } // [l, r) pii getHash(int l, int r){ int res, res2; res = (hs[r] - hs[l] * pw[r - l]) % P; res2 = (hs2[r] - hs2[l]*pw2[r-l])%P2; if(res < 0)res += P; if(res2 < 0)res2 += P2; return mp(res, res2); } }; string nstr(){ static const int MAX_LEN = 50010; static char res_[MAX_LEN]; scanf("%s",res_); return string(res_); } vector B[128]; vi C[128]; int main(){ string S = nstr(); RollingHash A(S); int M; cin >> M; rep(i, M){ string T = nstr(); B[T[0]].push_back(RollingHash(T).getHash(0, sz(T))); C[T[0]].push_back(sz(T)); } int N = sz(S), ans = 0; rep(i, N){ rep(j, sz(B[S[i]])){ int r = i + C[S[i]][j]; if(r <= N){ if(A.getHash(i, r) == B[S[i]][j]){ ++ans; } } } } cout << ans << endl; }