#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template struct Trie { struct Node { char c; int nx[char_sz]; std::vector tails; Node(char c) : c(c) { std::memset(nx, -1, sizeof(nx)); } }; std::vector nodes; Trie(const char basis = 'a') : basis(basis) { nodes.emplace_back('$'); } void add(const std::string &s, int id = -1, int pos = 0) { for (char c : s) { int now = convert(c); if (nodes[pos].nx[now] == -1) { int nx_pos = nodes.size(); nodes[pos].nx[now] = nx_pos; nodes.emplace_back(c); pos = nx_pos; } else { pos = nodes[pos].nx[now]; } } nodes[pos].tails.emplace_back(id); } int find(const std::string &t, int pos = 0) const { for (char c : t) { int now = convert(c); if (nodes[pos].nx[now] == -1) return -1; pos = nodes[pos].nx[now]; } return pos; } int convert(char c) const { return c - basis; } private: const char basis; }; template struct AhoCorasick : Trie { using Trie::Trie; std::vector cnt; void build(bool heavy = false) { is_built = true; is_heavy = heavy; auto &vertices = this->nodes; int n = vertices.size(); cnt.resize(n); for (int i = 0; i < n; ++i) { if (heavy) std::sort(vertices[i].tails.begin(), vertices[i].tails.end()); cnt[i] = vertices[i].tails.size(); } std::queue que; for (int i = 0; i < char_sz; ++i) { if (vertices[0].nx[i] == -1) { vertices[0].nx[i] = 0; } else { vertices[vertices[0].nx[i]].nx[char_sz] = 0; que.emplace(vertices[0].nx[i]); } } while (!que.empty()) { auto node = vertices[que.front()]; cnt[que.front()] += cnt[node.nx[char_sz]]; que.pop(); for (int i = 0; i < char_sz; ++i) { if (node.nx[i] == -1) continue; int on_failure = node.nx[char_sz]; while (vertices[on_failure].nx[i] == -1) on_failure = vertices[on_failure].nx[char_sz]; vertices[node.nx[i]].nx[char_sz] = vertices[on_failure].nx[i]; if (heavy) { std::vector &ver = vertices[node.nx[i]].tails, tmp; std::set_union(ver.begin(), ver.end(), vertices[vertices[on_failure].nx[i]].tails.begin(), vertices[vertices[on_failure].nx[i]].tails.end(), std::back_inserter(tmp)); ver.resize(tmp.size()); std::copy(tmp.begin(), tmp.end(), ver.begin()); } que.emplace(node.nx[i]); } } } int move(char c, int pos) const { // assert(is_built); int now = this->convert(c); while (this->nodes[pos].nx[now] == -1) pos = this->nodes[pos].nx[char_sz]; return pos = this->nodes[pos].nx[now]; } int match(const std::string &t, int pos = 0) const { assert(is_built); int total = 0; for (char c : t) { pos = move(c, pos); total += cnt[pos]; } return total; } std::map match_heavy(const std::string &t, int pos = 0) const { assert(is_built && is_heavy); std::map mp; for (char c : t) { pos = move(c, pos); for (int e : this->nodes[pos].tails) ++mp[e]; } return mp; } private: bool is_built = false, is_heavy = false; }; int main() { std::string s; std::cin >> s; AhoCorasick<> aho('A'); int m; std::cin >> m; for (int i = 0; i < m; ++i) { std::string p; std::cin >> p; aho.add(p, i); } aho.build(); std::cout << aho.match(s) << '\n'; return 0; }