#define PROBLEM "https://yukicoder.me/problems/no/430" #include using namespace std; template struct AhoCorasick { struct Node { vector children; Node* fail; vector output; Node() : children(ALPHA_SIZE, nullptr), fail(nullptr) {} }; Node* root; vector patterns; AhoCorasick() : root(new Node()) {} void insert(const string& word, int index) { Node* cur = root; for(char c : word) { int idx = c - 'a'; if(cur->children[idx] == nullptr) cur->children[idx] = new Node(); cur = cur->children[idx]; } cur->output.push_back(index); } void build() { queue q; root->fail = root; for(int i = 0; i < ALPHA_SIZE; i++) { if(root->children[i]) { root->children[i]->fail = root; q.push(root->children[i]); } else root->children[i] = root; } while(q.size()) { Node* cur = q.front(); q.pop(); for(int i = 0; i < ALPHA_SIZE; i++) { Node* child = cur->children[i]; if(child) { child->fail = cur->fail->children[i]; child->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end()); q.push(child); } else cur->children[i] = cur->fail->children[i]; } } } vector> search(const string& word) { vector> matches; Node* cur = root; for(int i = 0; i < (int)word.size(); i++) { int idx = word[i] - 'a'; cur = cur->children[idx]; for(int pat_idx : cur->output) matches.emplace_back(i, pat_idx); } return matches; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); string S; int M; cin >> S >> M; for(char& c : S) c += 32; AhoCorasick ac; for(int i = 0; i < M; i++) { string C; cin >> C; for(char& c : C) c += 32; ac.insert(C, i); } ac.build(); auto matches = ac.search(S); cout << matches.size() << "\n"; return 0; }