#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long MAX = 5100000; const long long INF = 1LL << 60; //const long long MOD = 1000000007LL; const long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; template struct RollingHash { vector hash, pows; ull base, mod; RollingHash(const T &a, ull base, ull mod = 1000000009) : hash(a.size() + 1), pows(a.size() + 1, 1), mod(mod), base(base) { for (int i = 0; i < a.size(); i++) { pows[i + 1] = pows[i] * base % mod; hash[i + 1] = hash[i] * base % mod + a[i]; if (hash[i + 1] >= mod) hash[i + 1] -= mod; } } // 現在の文字列のサイズ int size() { return hash.size() - 1; } // [l, r) ull get(int l, int r) { assert(l <= r); ull ret = hash[r] + mod - hash[l] * pows[r - l] % mod; if (ret >= mod) ret -= mod; return ret; } void concat(const T &b) { int n = hash.size() - 1, m = b.size(); pows.resize(n + m + 1); hash.resize(n + m + 1); for (int i = 0; i < m; i++) { pows[n + i + 1] = pows[n + i] * base % mod; hash[n + i + 1] = hash[n + i] * base % mod + b[i]; if (hash[n + i + 1] >= mod) hash[n + i + 1] -= mod; } } void pop_back() { hash.pop_back(); pows.pop_back(); } }; constexpr int HASH_NUM = 4; struct bases_t { int use[HASH_NUM]; int &operator[](int i) { return use[i]; } bases_t() { mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); for (int i = 0; i < HASH_NUM; i++) use[i] = rnd() % 10000; } } bases; using multihash_t = array; template > struct MultiRollingHash { vector> rhs; MultiRollingHash(const T &a) { for (int i = 0; i < HASH_NUM; i++) { rhs.push_back(RollingHash(a, bases[i])); } } multihash_t get(int l, int r) { multihash_t ret; for (int i = 0; i < HASH_NUM; i++) ret[i] = rhs[i].get(l, r); return ret; } int size() { return rhs[0].size(); } void concat(const T &b) { for (auto &rh : rhs) rh.concat(b); } void pop_back() { for (auto &rh : rhs) rh.pop_back(); } }; int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ string s; cin >> s; MultiRollingHash mrh(s); ll M; cin >> M; vector> vvs(11); for (ll i = 0; i < M; i++) { string t; cin >> t; MultiRollingHash rol(t); vvs[t.size()][rol.get(0,t.size())]++; } ll res = 0; for (ll len = 1; len <= 10; len++) { for (ll i = 0; i <= (ll)s.size() - len; i++) { if (vvs[len].find(mrh.get(i, i + len)) != vvs[len].end()) res += vvs[len][mrh.get(i, i + len)]; } } cout << res << endl; return 0; }