#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define _USE_MATH_DEFINES #include #include using namespace std; #define INFD numeric_limits::infinity() #define INFL (int)1e8 #define INFLL (long long)1e15 #define Loop(i, n) for(int i = 0; i < (int)n; i++) #define Loop1(i, n) for(int i = 1; i <= (int)n; i++) #define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--) #define Loopr1(i, n) for(int i = (int)n; i >= 1; i--) #define bitmanip(m,val) static_cast>(val) typedef long long int ll; typedef vector vi; typedef vector> vvi; typedef pair P; typedef pair Pll; typedef vector vll; typedef vector> vvll; /*******************************************************/ class Hash_String { private: int kind; char base; ll powll(ll n, ll p) { if (p == 0) return 1; else if (p == 1) return n; else { ll ans = powll(n, p / 2); ans = ans * ans; if (p % 2 == 1) ans = ans * n; return ans; } } vll hash_vec_accumulate(string a, int length) { int n = a.length(); if (n - length + 1 <= 0) return{}; vll ret(n - length + 1, 0); if (n == 0) return ret; ret[0] = make_hash_of(a.substr(0, length)); Loop1(i, ret.size() - 1) { ret[i] = ret[i - 1] / kind + powll(kind, length - 1) * (a[i + length - 1] - base); } return ret; } public: // only for consecutive charactors in ASCII Hash_String(int kind, char base) { Hash_String::kind = kind; Hash_String::base = base; } ll make_hash_of(string s) { ll ret = 0; ll x = 1; Loop(i, s.length()) { ret += (s[i] - base) * x; x *= kind; } return ret; } // return series of indexes, the hash of searched string must be less than 2^63 vvi search_str(string source, vector destination) { int n = source.length(); vvll hash_vecs(64); vvi ret(destination.size()); Loop(i, destination.size()) { int m = destination[i].length(); if (hash_vecs[m].empty()) { hash_vecs[m] = hash_vec_accumulate(source, m); } ll d_hash = make_hash_of(destination[i]); Loop(j, hash_vecs[m].size()) { if (d_hash == hash_vecs[m][j]) ret[i].push_back(j); } } return ret; } }; int main() { string s; cin >> s; int q; cin >> q; vector ts(q); Loop(i, q) { cin >> ts[i]; } Hash_String hs(26, 'A'); vvi result = hs.search_str(s, ts); int ans = 0; Loop(i, result.size()) { ans += result[i].size(); } cout << ans << endl; }