#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(); _pow1.resize(_n + 1); _pow2.resize(_n + 1); _hash1.resize(_n + 1); _hash2.resize(_n + 1); _pow1[0] = _pow2[0] = 1; _hash1[0] = _hash2[0] = 0; for(int i = 0; i < _n; i++){ _pow1[i + 1] = (_pow1[i] * _b1) % _mod1; _pow2[i + 1] = (_pow2[i] * _b2) % _mod2; _hash1[i + 1] = (S[i] + _hash1[i] * _b1) % _mod1; _hash2[i + 1] = (S[i] + _hash2[i] * _b2) % _mod2; } } pair GetHash(void){ return make_pair(_hash1[_n], _hash2[_n]); } pair GetHash(int l, int r){ int h1, h2; h1 = ((_hash1[r] - _hash1[l] * _pow1[r - l]) % _mod1 + _mod1) % _mod1; h2 = ((_hash2[r] - _hash2[l] * _pow2[r - l]) % _mod2 + _mod2) % _mod2; return make_pair(h1, h2); } private: int _n; long long _b1 = 1009, _b2 = 1007; long long _mod1 = 1e9 + 7, _mod2 = 1e9 + 9; vector _pow1, _pow2; vector _hash1, _hash2; }; 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); 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; }