#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() class RollingHash{ public: RollingHash(const string &S) { _N = S.length(); _Bs.resize(_N + 1); _Hs.reserve(_N + 1); _Bs[0] = 1ULL; _Hs[0] = 0ULL; for(auto i = 0; i < _N; i++){ _Bs[i + 1] = _Bs[i] * _B; _Hs[i + 1] = S[i] + _Hs[i] * _B; } } unsigned long long GetHash(void){ return _Hs[_N]; } unsigned long long GetHash(int l, int r){ return _Hs[r] - _Hs[l] * _Bs[r - l]; } private: unsigned long long _B = 1e9 + 7; vector _Bs; vector _Hs; int _N; }; int main() { string S; cin >> S; int N = S.length(); int M; cin >> M; VS C(M); REP(i, M) cin >> C[i]; RollingHash RH(S); RH.GetHash(0, 0); int ret = 0; REP(i, M){ int m = C[i].length(); RollingHash R(C[i]); REP(j, N - m + 1){ if(R.GetHash() == RH.GetHash(j, j + m)) ret++; } } cout << ret << endl; return 0; }