#include using namespace std; template using min_priority_queue = priority_queue,greater>; template void printv(vector &v){ bool b = false; for(auto i : v){ if(b) cout << " "; else b = true; cout << i; } cout << endl; } int64_t rand64(){ int64_t l = rand(); int64_t r = rand(); return (l<<31)+r; } template bool chmin(T &a, const T& b) { if (a > b) { a = b; // aをbで更新 return true; } return false; } template bool chmax(T &a, const T& b) { if (a < b) { a = b; // aをbで更新 return true; } return false; } const uint64_t rh_mod = 0x1FFFFFFFFFFFFFFF; const uint64_t rh_mask30 = 0x3FFFFFFF; const uint64_t rh_mask31 = 0x7FFFFFFF; const uint64_t rh_mask61 = rh_mod; uint64_t rh_base; vector rh_base_pow; uint64_t rh_mul(uint64_t a, uint64_t b){ uint64_t au = a >> 31; uint64_t ad = a & rh_mask31; uint64_t bu = b >> 31; uint64_t bd = b & rh_mask31; uint64_t mid = ad * bu + au * bd; uint64_t midu = mid >> 30; uint64_t midd = mid & rh_mask30; uint64_t x = au * bu * 2 + midu + (midd << 31) + ad * bd; uint64_t xu = x >> 61; uint64_t xd = x & rh_mask61; uint64_t rtn = xu + xd; if(rtn >= rh_mod) rtn -= rh_mod; return rtn; } struct monoid_rolling_hash{ uint64_t val; int size; monoid_rolling_hash(){ val = 0; size = 0; } monoid_rolling_hash(char c){ val = (int)c; size = 1; } monoid_rolling_hash e(){ return monoid_rolling_hash(); } monoid_rolling_hash operator*(monoid_rolling_hash other){ monoid_rolling_hash rtn; rtn.size = size + other.size; rtn.val = rh_mul(val, rh_base_pow[other.size]) + other.val; if(rtn.val >= rh_mod) rtn.val -= rh_mod; return rtn; } monoid_rolling_hash(string &s){ monoid_rolling_hash rtn; for(char &c : s){ rtn = rtn * monoid_rolling_hash(c); } val = rtn.val; size = rtn.size; } }; void init_rh_base(int N){ rh_base = (uint64_t(1) << 32) + rand(); rh_base_pow.resize(N); rh_base_pow[0] = 1; for(int i = 1; i < N; i++){ rh_base_pow[i] = rh_mul(rh_base_pow[i-1], rh_base); } } template struct segtree{ int sz; vector dat; segtree(){ ; } segtree(int n){ sz = 1; while(sz <= n) sz *= 2; dat.resize(2*sz-1, monoid().e()); } void update(int k, monoid a){ k += sz-1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = dat[2*k+1]*dat[2*k+2]; } } void plus(int k, monoid a){ update(k, get(k, k+1)*a); } //[a,b) monoid get(int a, int b){ return sub_get(a, b, 0, 0, sz); } monoid sub_get(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return monoid().e(); if(a <= l && r <= b) return dat[k]; monoid vl = sub_get(a, b, 2*k+1, l, (l+r)/2); monoid vr = sub_get(a, b, 2*k+2, (l+r)/2, r); return vl*vr; } }; bool yn(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; return b; } bool debug; bool randomInput; bool debugOutput; int numOfTestCase; using ans_type = int; void input(){ if(numOfTestCase > 1){ } if(randomInput){ } else{ } return; } void output_input(){ ; } ans_type calc(){ string S; int N, M; cin >> S >> M; N = S.size(); int C_max_size = 10; vector C(M); for(auto &s : C) cin >> s; init_rh_base(N); segtree seg(N); for(int i = 0; i < N; i++){ seg.update(i, monoid_rolling_hash(S[i])); } map rh_map; for(int l = 0; l < N; l++){ for(int r = l+1; r <= N && r <= l + C_max_size; r++){ rh_map[seg.get(l, r).val]++; //cout << S.substr(l, r-l) << " " << seg.get(l, r).val << endl; } } int ans = 0; for(auto s : C){ ans += rh_map[monoid_rolling_hash(s).val]; //cout << s << " " << monoid_rolling_hash(s).val << endl; } cout << ans << endl; return ans_type(); } ans_type calc_simple(){ return ans_type(); } void output(ans_type ans){ return; } int main(){ debug = 0; randomInput = 0; debugOutput = 0; numOfTestCase = 1; srand(time(NULL)); cout << fixed << setprecision(12); if(numOfTestCase == 0) cin >> numOfTestCase; if(debug){ for(int i = 0; i < numOfTestCase; i++){ if(debugOutput) cout << string(16, '-') << endl; input(); ans_type ans = calc(); ans_type ansSimple = calc_simple(); if(ans != ansSimple){ output_input(); output(ans); output(ansSimple); } } } else{ for(int i = 0; i < numOfTestCase; i++){ input(); output(calc()); } } return 0; }