#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } struct RollingHash { static const uint64_t MOD = (1ull << 61) - 1; static const uint64_t MASK30 = (1ull << 30) - 1; static const uint64_t MASK31 = (1ull << 31) - 1; static const uint64_t MASK61 = MOD; vector< uint64_t > hashed, power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= MOD) a -= MOD; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint64_t LA = a >> 31; uint64_t RA = a & MASK31; uint64_t LB = b >> 31; uint64_t RB = b & MASK31; uint64_t M = RA * LB + LA * RB; uint64_t LM = M >> 30; uint64_t RM = M & MASK30; return CalcMod(LA * LB * 2 + LM + (RM << 31) + RA * RB); } static inline uint64_t CalcMod(uint64_t X){ uint64_t LX = X >> 61; uint64_t RX = X & MASK61; uint64_t res = LX + RX; if (res >= MOD) res -= MOD; return res; } static inline uint64_t generate_base() { mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution< uint64_t > rand(1, RollingHash::MOD - 1); return rand(mt); } RollingHash() = default; RollingHash(const string &s, uint64_t base) : base(base) { size_t sz = s.size(); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for(int i = 0; i < sz; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = add(mul(hashed[i], base), s[i]); } } template< typename T > RollingHash(const vector< T > &s, uint64_t base) : base(base) { size_t sz = s.size(); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for(int i = 0; i < sz; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = add(mul(hashed[i], base), s[i]); } } uint64_t query(int l, int r) const { return add(hashed[r], MOD - mul(hashed[l], power[r - l])); } uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) const { return add(mul(h1, power[h2len]), h2); } int lcp(const RollingHash &b, int l1, int r1, int l2, int r2) const { assert(base == b.base); int len = min(r1 - l1, r2 - l2); int low = 0, high = len + 1; while(high - low > 1) { int mid = (low + high) / 2; if(query(l1, l1 + mid) == b.query(l2, l2 + mid)) low = mid; else high = mid; } return low; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); string S; int M; cin >> S >> M; auto B = RollingHash::generate_base(); auto rhs = RollingHash(S, B); map cnt; int N = S.length(); for(int i = 0; i < N; ++i){ for(int k = 1; k <= 10; ++k){ cnt[rhs.query(i, i + k)] += 1; } } int64_t ans = 0; for(int i = 0; i < M; ++i){ string T; cin >> T; auto rht = RollingHash(T, B); int n = T.length(); ans += cnt[rht.query(0, n)]; } cout << ans << endl; return 0; }