#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++) #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++) #define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--) #define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--) #define PI acos(-1.0) #define DEBUG(C) cerr << C << endl; #define VI vector #define VII vector #define VL vector #define VLL vector #define VD vector #define VDD vector #define PII pair #define PDD pair #define PLL pair #define VPII vector #define ALL(a) (a).begin(), (a).end() #define SORT(a) sort(ALL(a)) #define REVERSE(a) reverse(ALL(a)) #define MP make_pair #define EB emplace_back #define FORE(a, b) for (auto &&a:b) #define FIND(s, n) (s.find(n) != s.end()) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9; const int MOD = INF + 7; const LL LLINF = 1e18; class RollingHash { private: const LL mods[2] = {(LL)(1e9 + 7), (LL)(1e9 + 9)}; vector hs[2], pow[2]; vector x; //基数 int len; string S; public: //文字列, 基数1, 基数2 RollingHash(const string& str, long long num1, long long num2) { x.resize(2); x[0] = num1; x[1] = num2; S = str; init(S); } void init(const string& str) { len = str.length(); for (int i = 0; i < 2; i++) { hs[i].resize(len + 5); pow[i].resize(len + 5); pow[i][0] = 1; for (int j = 0; j < len; j++) { pow[i][j + 1] = (pow[i][j] * x[i]) % mods[i]; } } for (int i = 0; i < 2; i++) { for (int j = 0; j < len; j++) { hs[i][j + 1] = (hs[i][j] + pow[i][j] * (long long)str[j]) % mods[i]; } } } pair makeHash(const string& str) { long long res[2]; int slen = str.length(); for (int i = 0; i < 2; i++) { res[i] = 0; for (int j = 0;j < slen; j++) { res[i] = (res[i] + pow[i][j] * (long long)str[j]) % mods[i]; } } return make_pair(res[0], res[1]); } pair , vector > getHash() { return make_pair(hs[0], hs[1]); } //引数の文字列と一致する場所 //引数の文字列と一致する数 int matchNum(const string& str) { auto p = makeHash(str); int res = 0; int slen = str.length(); for (int i = slen; i < len + 1; i++) { LL hs1 = (hs[0][i] - hs[0][i - slen] + mods[0]) % mods[0]; LL hs2 = (hs[1][i] - hs[1][i - slen] + mods[1]) % mods[1]; res += (p == MP(hs1, hs2)); p.first = p.first * x[0] % mods[0]; p.second = p.second * x[1] % mods[1]; } return res; } }; int main(void) { string S; cin >> S; RollingHash r(S, 1234567, 8901234); int M; cin >> M; int ans = 0; REP(i, M) { string s; cin >> s; ans += r.matchNum(s); } cout << ans << endl; return 0; }