#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; template using posteriority_queue = priority_queue, greater >; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; // const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[] = {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; } int popcount(int val) { return __builtin_popcount(val); } int popcountll(ll val) { return __builtin_popcountll(val); } template void unique(vector &a) { a.erase(unique(ALL(a)), a.end()); } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; template struct Trie { struct Node { char c; int nx[char_sz]; vector tails; Node(char c) : c(c) { memset(nx, -1, sizeof(nx)); } }; vector nodes; Trie(char basis = 'a') : basis(basis) { nodes.emplace_back('$'); } void add(const 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 string &t, int pos = 0) { 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) { return c - basis; } private: char basis; }; template struct AhoCorasick : Trie { using Trie::Trie; vector cnt; void build() { auto &vertices = this->nodes; int n = vertices.size(); cnt.resize(n); REP(i, n) { sort(ALL(vertices[i].tails)); cnt[i] = vertices[i].tails.size(); } queue que; REP(i, char_sz) { 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(); REP(i, char_sz) if (node.nx[i] != -1) { 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]; auto &ver = vertices[node.nx[i]].tails; vector tmp; set_union(ALL(ver), ALL(vertices[vertices[on_failure].nx[i]].tails), back_inserter(tmp)); ver.resize(tmp.size()); copy(ALL(tmp), ver.begin()); que.emplace(node.nx[i]); } } } int move(char c, int pos) { 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 string &t, int pos = 0) { int total = 0; for (char c : t) { pos = move(c, pos); total += this->nodes[pos].tails.size(); } return total; } map match_heavy(const string &t, int pos = 0) { map mp; for (char c : t) { pos = move(c, pos); for (int e : this->nodes[pos].tails) ++mp[e]; } return mp; } }; int main() { string s; cin >> s; AhoCorasick<> aho('A'); int m; cin >> m; REP(i, m) { string p; cin >> p; aho.add(p, i); } aho.build(); cout << aho.match(s) << '\n'; return 0; }