#include using namespace std; #define rep(i, n) for(int i = 0; i < n; i++) #define rep2(i, x, n) for(int i = x; i <= n; i++) #define rep3(i, x, n) for(int i = x; i >= n; i--) #define elif else if #define sp(x) fixed << setprecision(x) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; const ll MOD = 1000000007; //const ll MOD = 998244353; const int inf = (1<<30)-1; const ll INF = (1LL<<60)-1; const double pi = acos(-1.0); const double EPS = 1e-10; template bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;}; template bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;}; //ローリングハッシュ //計算量 構築:O(N)、ハッシュクエリ:O(1) struct Random_Number_Generator { mt19937 mt; Random_Number_Generator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} int operator () (int l, int r){ uniform_int_distribution dist(l, r-1); return dist(mt); } int operator () (int r){ return (*this)(0, r); } }; using ull = unsigned long long; struct Rolling_Hash{ const ull mod = (1ull<<61)-1; ull calc_mod(ull x){ ull ret = (x>>61) + x&mod; return ret - (ret >= mod? mod : 0); } ull mul(ull x, ull y){ x = calc_mod(x), y = calc_mod(y); ull x1 = x>>31, x2 = x&((1ull<<31)-1), y1 = y>>31, y2 = y&((1ull<<31)-1); ull z = x1*y2 + x2*y1, z1 = z>>30, z2 = z&((1ull<<30)-1); return calc_mod(x1*y1*2 + x2*y2 + z1 + (z2<<31)); } ull pow(ull x, int n){ ull ret = 1; while(n){ if(n&1) ret = mul(ret, x); x = mul(x, x), n >>= 1; } return ret; } ull base; vector hashed, pw; void set_base(){ Random_Number_Generator rnd; while(true){ int k = rnd(inf); if(gcd(mod-1, k) != 1) continue; base = pow(3, k); if(base < 256) continue; break; } } Rolling_Hash(const string &s){ set_base(); int n = sz(s); hashed.resize(n+1), pw.resize(n+1); hashed[0] = 0, pw[0] = 1; rep(i, n){ pw[i+1] = mul(pw[i], base); hashed[i+1] = mul(hashed[i], base) + s[i]; if(hashed[i+1] >= mod) hashed[i+1] -= mod; } } ull query(int l, int r){ ull ret = hashed[r] + mod - mul(hashed[l], pw[r-l]); return ret - (ret >= mod? mod : 0); } ull get_hash(const string &s){ ull ret = 0; rep(i, sz(s)){ ret = mul(ret, base) + s[i]; if(ret >= mod) ret -= mod; } return ret; } }; int main(){ string S; int M; cin >> S >> M; Rolling_Hash rh(S); set s; rep(i, M){ string T; cin >> T; s.insert(rh.get_hash(T)); } int ans = 0; rep(i, sz(S)){ rep2(j, 1, 10){ if(i+j > sz(S)) continue; ull hash = rh.query(i, i+j); if(s.count(hash)) ans++; } } cout << ans << endl; }