#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vec; typedef vector mat; #define rep(i, n) for(ll i = 0; i < (n); i++) #define revrep(i, n) for(ll i = (n-1); i >= 0; i--) #define pb push_back #define f first #define s second ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll max3(ll a, ll b, ll c){return max(a, max(b, c));}; ll min3(ll a, ll b, ll c){return min(a, min(b, c));}; ll max4(ll a, ll b, ll c, ll d){return max(max(a, b), min(c, d));}; ll min4(ll a, ll b, ll c, ll d){return min(min(a, b), min(c, d));}; ll max5(ll a, ll b, ll c, ll d, ll e){return max(max(a, b), max3(c, d, e));}; ll min5(ll a, ll b, ll c, ll d, ll e){return min(min(a, b), min3(c, d, e));}; const ll INFL = 1LL << 60;//10^18 = 2^60 const int INF = 1 << 30;//10^9 ll MOD = 1000000007; //ll MOD = 998244353; vector dy = {0, 0, 1, -1, 1, 1, -1, -1, 0}; vector dx = {1, -1, 0, 0, 1, -1, 1, -1, 0}; ll pow_long(ll x, ll k){ ll res = 1; while(k > 0){ if(k % 2) res *= x; x *= x; k /= 2; } return res; } ll pow_mod(ll x, ll k){ x %= MOD; x += MOD; x %= MOD; ll res = 1; while(k > 0){ if(k % 2){ res *= x; res %= MOD; } x *= x; x %= MOD; k /= 2; } return res; } ll inverse(ll x){return pow_mod(x, MOD - 2);}; ll gcd(ll a, ll b){ if(b == 0) return a; return gcd(b, a % b); } ll lcm(ll x, ll y){return x / gcd(x, y) * y;}; ll kai_mod(ll x){ if(x == 0) return 1; return x * kai_mod(x-1) % MOD; } /* //コンビネーション const int MAXcomb = 200010; ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb]; //facはn!,finvは1/n! //invは逆元 void COMinit(){ fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(int i = 2; i < MAXcomb; i++){ fac[i] = fac[i-1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD; finv[i] = finv[i-1] * inv[i] % MOD; } } ll comb(int n, int k){ if(n < k) return 0; if(n < 0 || k < 0) return 0; return fac[n] * finv[k] % MOD * finv[n-k] % MOD; } */ int n, k; const int MAX_N = 1000010; int Rank[MAX_N + 1]; int tmp[MAX_N + 1]; //(rank[i], rank[i+k])と(rank[j], rank[j+k])を比較 bool compare_sa(int i, int j){ if(Rank[i] != Rank[j]) return Rank[i] < Rank[j]; else{ int ri = i + k <= n ? Rank[i + k] : -1; int rj = j + k <= n ? Rank[j + k] : -1; return ri < rj; } } //文字列の接尾辞配列を構築 void construst_sa(string S, int *sa){ n = S.length(); //最初は1文字、ランクは文字コードにすればよい for(int i = 0; i <= n; i++){ sa[i] = i; Rank[i] = i < n ? S[i] : -1; } //k文字についてソートされているところから、2k文字でソートする for(k = 1; k <= n; k*=2){ sort(sa, sa + n + 1, compare_sa); //いったんtmpに次のランクを計算し、それからRankに移す tmp[sa[0]] = 0; for(int i = 1; i <= n; i++){ tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for(int i = 0; i <= n; i++){ Rank[i] = tmp[i]; } } } int contain(string S, int *sa, string T){ int a = 0, b = S.length(); while(b - a > 1){ int c = (a + b) / 2; //Sのsa[c]文字目から|T|文字と比較 if(S.compare(sa[c], T.length(), T) < 0) a = c; else b = c; } int res = 0; while(b <= n){ if(S.compare(sa[b], T.length(), T) == 0) res++; else break; b++; } return res; } string S; int sa[1000010]; int main(){ cin >> S; construst_sa(S, sa); ll M; cin >> M; ll cnt = 0; rep(i, M){ string T; cin >> T; cnt += contain(S, sa, T); } cout << cnt << endl; }