#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef vector VI; typedef vector VVI; typedef vector VS; typedef pair PII; typedef long long LL; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define MP make_pair #define MT make_tuple #define EACH(i,c) for(auto i: c) #define SORT(c) sort((c).begin(),(c).end()) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() unsigned long long B = 1e9 + 7; unsigned long long hs[50001], Bs[50001]; void init(string S){ int N = S.length(); hs[0] = 0; Bs[0] = 1; REP(i, N){ hs[i + 1] = S[i] + hs[i] * B; Bs[i + 1] = Bs[i] * B; } } unsigned long long f(int i, int j){ return hs[j] - hs[i] * Bs[j - i]; } unsigned long long gethash(string S){ unsigned long long ret = 0; EACH(c, S) ret = c + ret * B; return ret; } int main() { string S; cin >> S; int N = S.length(); int M; cin >> M; VS C(M); REP(i, M) cin >> C[i]; init(S); int ret = 0; REP(i, M){ auto h = gethash(C[i]); int m = C[i].length(); REP(j, N - m + 1){ if(h == f(j, j + m)) ret++; } } cout << ret << endl; return 0; }