#include #include #include using namespace std; using namespace atcoder; using M1 = modint1000000007; using M2 = modint998244353; using hash_t = pair; namespace atcoder { bool operator<(const M1 &t1, const M1 &t2) { return t1.val() < t2.val(); } bool operator<(const M2 &t1, const M2 &t2) { return t1.val() < t2.val(); } } // namespace atcoder struct Hash { int n; string s; static long long B; bool calc_rev; fenwick_tree bit1, bit1_rev; fenwick_tree bit2, bit2_rev; vector Bp1, Bp1_inv; vector Bp2, Bp2_inv; Hash() {} Hash(string &s, bool calc_rev = true) : s(s), n(s.length()), calc_rev(calc_rev), Bp1(n + 1), Bp2(n + 1) { Bp1_inv.resize(n + 1), Bp2_inv.resize(n + 1); bit1 = fenwick_tree(n); bit2 = fenwick_tree(n); M1 p1 = 1; M2 p2 = 1; Bp1[0] = Bp1_inv[0] = 1, Bp2[0] = Bp2_inv[0] = 1; for (int i = 0; i < n; i++) { bit1.add(i, p1 * s[i]); bit2.add(i, p2 * s[i]); p1 *= B, p2 *= B; Bp1[i + 1] = p1; Bp2[i + 1] = p2; Bp1_inv[i + 1] = p1.inv(); Bp2_inv[i + 1] = p2.inv(); } if (not calc_rev) return; bit1_rev = fenwick_tree(n); bit2_rev = fenwick_tree(n); for (int i = 0; i < n; i++) { bit1_rev.add(i, Bp1[n - i - 1] * s[i]); bit2_rev.add(i, Bp2[n - i - 1] * s[i]); } } void update(int i, char c) { bit1.add(i, Bp1[i] * c - bit1.sum(i, i + 1)); bit2.add(i, Bp2[i] * c - bit2.sum(i, i + 1)); if (not calc_rev) return; bit1_rev.add(i, Bp1[n - i - 1] * c - bit1_rev.sum(i, i + 1)); bit2_rev.add(i, Bp2[n - i - 1] * c - bit2_rev.sum(i, i + 1)); } hash_t query(int l, int r, bool rev = false) { assert(l <= r); if (rev) { assert(calc_rev); hash_t res = {bit1_rev.sum(l, r), bit2_rev.sum(l, r)}; res.first *= Bp1_inv[n - r]; res.second *= Bp2_inv[n - r]; return res; } hash_t res = {bit1.sum(l, r), bit2.sum(l, r)}; res.first *= Bp1_inv[l]; res.second *= Bp2_inv[l]; return res; } bool is_palindrome(int l, int r) { assert(calc_rev); return query(l, (l + r) / 2, false) == query((l + r + 1) / 2, r, true); } hash_t calc_hash(string &t) { hash_t res = {0, 0}; M1 p1 = 1; M2 p2 = 1; for (int i = 0; i < t.length(); i++) { res.first += p1 * t[i]; res.second += p2 * t[i]; p1 *= B, p2 *= B; } return res; } }; random_device B_seed; mt19937 B_engine(B_seed()); long long Hash::B = (long long)(B_engine()) + 1000; int main() { string s; int m; cin >> s >> m; Hash hash(s, false); map cnt; for (int len = 1; len <= 10; len++) { for (int i = 0; i + len <= s.length(); i++) { cnt[hash.query(i, i + len)]++; } } int ans = 0; for (int i = 0; i < m; i++) { string c; cin >> c; hash_t h = hash.calc_hash(c); ans += cnt[h]; } cout << ans << "\n"; }