#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fs first #define sc second using namespace std; typedef long long ll; typedef pair P; typedef pair T; const ll mod = 1000000007; ll fact[200200]; ll invfact[200200]; inline ll take_mod(ll a){ return (a % mod + mod) % mod; } inline ll add(ll a, ll b){ return take_mod(a+b); } inline ll sub(ll a, ll b){ return take_mod(a-b); } inline ll mul(ll a, ll b){ return take_mod(a * b); } inline ll pow(ll x, ll n){ ll res = 1LL; while(n > 0){ if(n & 1) res = mul(res, x); x = mul(x, x); n >>= 1; } return res; } ll mod_inv(ll x){ return pow(x, mod-2); } // nは上限 void make_fact(ll n){ fact[0] = 1; ll res = 1; for(int i = 1; i <= n; i++){ fact[i] = res; res = mul(res, i+1); } } // nは上限 void make_invfact(ll n){ invfact[0] = 1; invfact[n] = mod_inv(fact[n]); for(int i = n-1; i >= 1; i--){ invfact[i] = mul(invfact[i + 1], i + 1); } } ll perm(ll n, ll k){ return mul(fact[n], invfact[n-k]); } ll comb(ll n, ll k){ return mul(mul(fact[n], invfact[n-k]), invfact[k]); } class RollingHash{ public: map hash; RollingHash(){ } void add(ll hash_num){ if(hash.find(hash_num) == hash.end()){ hash[hash_num] = 1; } else { hash[hash_num] += 1; } } int search(ll hash_num){ if(hash.find(hash_num) == hash.end()){ return 0; } else{ return hash[hash_num]; } } }; int main(){ RollingHash rh = RollingHash(); ll powList[11]; powList[0] = 1; for(int i = 1; i < 11; i++){ powList[i] = (ll)(27) * powList[i-1]; } string s; cin >> s; for(int i = 1; i <= 10; i++){ ll hashNum = 0; for(int j = 0; j < s.length(); j++){ if(j - i >= 0){ hashNum -= (s[j-i] - 'A' + 1) * powList[i-1]; } hashNum *= 27; hashNum += s[j] - 'A' + 1; if(j - i + 1 >= 0){ // cout << hashNum << endl; rh.add(hashNum); } } } int M; cin >> M; int res = 0; for(int i = 0; i < M; i++){ string c; cin >> c; ll hashNum = 0; for(int j = 0; j < c.length(); j++){ hashNum *= 27; hashNum += c[j] - 'A' + 1; } res += rh.search(hashNum); // cout << res << endl; } cout << res << endl; return 0; }