#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; typedef long long ll; using ull = unsigned long long; 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; } template T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; } mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); constexpr long long INF = 1LL << 60; constexpr int inf = 1000000007; //constexpr long long mod = 1000000007LL; constexpr long long mod = 998244353; constexpr int MAX = 1100000; template struct TrieNode { array nxt; int cnt; vector accept; TrieNode() :cnt(0) { fill(nxt.begin(), nxt.end(), -1); } }; template struct Trie { using Node = TrieNode; vector nodes; int root; Trie() :root(0) { nodes.emplace_back(Node()); } void add(const vector& str, int id) { int node_index = 0; for (auto& c : str) { if (nodes[node_index].nxt[c] == -1) { nodes[node_index].nxt[c] = (int)nodes.size(); nodes.emplace_back(Node()); } nodes[node_index].cnt += 1; node_index = nodes[node_index].nxt[c]; } nodes[node_index].cnt += 1; nodes[node_index].accept.emplace_back(id); } void add(const vector& str) { add(str, nodes[0].cnt); } int find(const vector& str) { int node_index = 0; for (auto& c : str) { if (nodes[node_index].nxt[c] == -1) return -1; node_index = nodes[node_index].nxt[c]; } return node_index; } int count() const { return nodes[0].cnt; } int size() const { return nodes.size(); } }; template struct AhoCorasick : Trie { using Trie::Trie; const int FAIL = char_size; vector correct; void build(bool heavy = true) { correct.resize(this->size()); for (int i = 0; i < correct.size(); i++) correct[i] = (int)this->nodes[i].accept.size(); queue q; for (int i = 0; i <= char_size; i++) { if (this->nodes[0].nxt[i] >= 0) { this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0; q.emplace(this->nodes[0].nxt[i]); } else this->nodes[0].nxt[i] = 0; } while (!q.empty()) { auto& cur = this->nodes[q.front()]; int fail = cur.nxt[FAIL]; correct[q.front()] += correct[fail]; q.pop(); for (int i = 0; i < char_size; i++) { if (cur.nxt[i] >= 0) { this->nodes[cur.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i]; if (heavy) { auto& u = this->nodes[cur.nxt[i]].accept; auto& v = this->nodes[this->nodes[fail].nxt[i]].accept; vector accept; accept.reserve(u.size() + v.size()); set_union(u.begin(), u.end(), v.begin(), v.end(), back_inserter(accept)); u = accept; } q.emplace(cur.nxt[i]); } else cur.nxt[i] = this->nodes[fail].nxt[i]; } } } vector match(vector& str, bool heavy = true) { vector ret(heavy ? this->size() : 1); int cur = 0; for (auto& c : str) { cur = this->nodes[cur].nxt[c]; if (heavy) for (auto& v : this->nodes[cur].accept) ret[v] += 1; else ret[0] += correct[cur]; } return ret; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); string s; cin >> s; int m; cin >> m; auto enc = [](string s)->vector { vector ret(s.size()); for (int i = 0; i < s.size(); i++) { ret[i] = s[i] - 'A'; } return ret; }; AhoCorasick<26> aho; while (m--) { string c; cin >> c; auto v = enc(c); aho.add(v); } aho.build(false); auto v = enc(s); cout << aho.match(v, false)[0] << "\n"; }