#include #define rep(i,n) for (int i = 0; i < (n); ++i) #define rrep(i,n) for (int i = (n)-1; i >= 0; i--) #define rep2(i,s,n) for (int i = (s); i < (n); ++i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define vi vector #define vvi vector> #define vl vector #define vvl vector> #define vd vector #define vs vector #define vc vector #define vb vector #define vp vector

using namespace std; using ll = long long; using P = pair; using LP = pair; template istream& operator>>(istream &is,pair &p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream &os,const pair &p) { return os<<'{'< istream& operator>>(istream &is,vector &v) { for(T &t:v){is>>t;} return is; } template ostream& operator<<(ostream &os,const vector &v) { os<<'[';rep(i,v.size())os< bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;} template bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;} const int inf = 1001001001; const ll linf = 1001001001001001001; using ull = unsigned long long; const ull mod = (1ul<<61)-1; const ull mask30 = (1ul<<30)-1; const ull mask31 = (1ul<<31)-1; const ull mask61 = mod; ull calc_mod(ull x) { ull xu = x>>61; ull xd = x&mask61; ull res = xu+xd; if(res >= mod) res -= mod; return res; } // a*b mod 2^61-1 ull mul(ull a,ull b) { ull au = a>>31; ull ad = a&mask31; ull bu = b>>31; ull bd = b&mask31; ull mid = ad*bu+au*bd; ull midu = mid>>30; ull midd = mid&mask30; return au*bu*2+midu+(midd<<31)+ad*bd; } class rolling_hash { ull base1; ull base2; int n; string s; vector hash1,hash2,pow1,pow2; void init() { random_device rnd; mt19937_64 mt(rnd()); base1 = calc_mod(mt()); base2 = calc_mod(mt()); while(base1 < 2 || base1 > mod-2) base1 = calc_mod(mt()); while(base2 < 2 || base2 > mod-2) base2 = calc_mod(mt()); hash1.assign(n+1,0); hash2.assign(n+1,0); pow1.assign(n+1, 1); pow2.assign(n+1,1); rep(i,n) { hash1[i+1] = calc_mod(mul(hash1[i],base1)+s[i]); hash2[i+1] = calc_mod(mul(hash2[i],base2)+s[i]); pow1[i+1] = calc_mod(mul(pow1[i], base1)); pow2[i+1] = calc_mod(mul(pow2[i], base2)); } } public: rolling_hash(string s):s(s),n(s.size()) { init(); } // return hash of [l,r) pair get(int l,int r) { ll res1 = calc_mod(hash1[r]+mod*4-mul(hash1[l], pow1[r-l])); ll res2 = calc_mod(hash2[r]+mod*4-mul(hash2[l], pow2[r-l])); return make_pair(res1,res2); } int count(string t) { if(t.size() > n) return 0; ull ht1 = 0,ht2 = 0; rep(i,t.size()) { ht1 = calc_mod(mul(ht1,base1)+t[i]); ht2 = calc_mod(mul(ht2,base2)+t[i]); } pair ht = make_pair(ht1,ht2); int res = 0; rep(i,n-t.size()+1) { if(get(i,i+t.size()) == ht) res++; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string s; int m; cin >> s >> m; int ans = 0; rolling_hash rh(s); rep(i,m) { string c; cin >> c; ans += rh.count(c); } cout << ans << endl; }