Buzzwords

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    TrieNode* failLink = nullptr;
    int outputCount = 0;
    bool isEnd = false;
};

void insertPattern(TrieNode* root, const string& pattern) {
    TrieNode* current = root;
    for (char c : pattern) {
        if (current->children.find(c) == current->children.end()) {
            current->children[c] = new TrieNode();
        }
        current = current->children[c];
    }
    current->isEnd = true;
    current->outputCount++;  
}

void buildFailureLinks(TrieNode* root) {
    queue<TrieNode*> q;
    root->failLink = root; 
    for (auto& child : root->children) {
        child.second->failLink = root;
        q.push(child.second);
    }

    while (!q.empty()) {
        TrieNode* current = q.front();
        q.pop();

        for (auto& child : current->children) {
            char ch = child.first;
            TrieNode* nextNode = child.second;

            TrieNode* fail = current->failLink;
            while (fail != root && fail->children.find(ch) == fail->children.end()) {
                fail = fail->failLink;
            }
            if (fail->children.find(ch) != fail->children.end()) {
                nextNode->failLink = fail->children[ch];
            } else {
                nextNode->failLink = root;
            }
            
            if (nextNode->failLink->isEnd) {
                nextNode->outputCount += nextNode->failLink->outputCount;
            }
            q.push(nextNode);
        }
    }
}

int searchText(TrieNode* root, const string& text) {
    TrieNode* current = root;
    int totalCount = 0;

    for (char c : text) {
        while (current != root && current->children.find(c) == current->children.end()) {
            current = current->failLink;
        }
        if (current->children.find(c) != current->children.end()) {
            current = current->children[c];
        }

        if (current->isEnd) {
            totalCount += current->outputCount;
        }
    }
    return totalCount;
}

int main() {
    string text;
    getline(cin, text);
    int q;
    cin >> q;
    cin.ignore();

    TrieNode* root = new TrieNode();

    for (int i = 0; i < q; i++) {
        string buzzword;
        getline(cin, buzzword);
        insertPattern(root, buzzword);
    }

    buildFailureLinks(root);

    int result = searchText(root, text);
    cout << result << endl;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER