Buzzwords

input/code.cpp: In function 'std::vector<TrieNode> buildTrie(const std::vector<std::__cxx11::basic_string<char> >&)':
input/code.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < patterns.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int ahoCorasick(const string&, const std::vector<std::__cxx11::basic_string<char> >&)':
input/code.cpp:77:18: warning: unused variable 'patternIndex' [-Wunused-variable]
   77 |         for (int patternIndex : trie[state].outputs) {
      |                  ^~~~~~~~~~~~

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

using namespace std;

struct TrieNode {
    unordered_map<char, int> children;
    int failure = 0;
    vector<int> outputs;
};

vector<TrieNode> buildTrie(const vector<string>& patterns) {
    vector<TrieNode> trie(1);

    for (int i = 0; i < patterns.size(); ++i) {
        int state = 0;
        for (char c : patterns[i]) {
            if (trie[state].children.find(c) == trie[state].children.end()) {
                trie[state].children[c] = trie.size();
                trie.emplace_back();
            }
            state = trie[state].children[c];
        }
        trie[state].outputs.push_back(i);
    }

    // Failure links
    queue<int> q;
    for (auto& p : trie[0].children) {
        trie[p.second].failure = 0;
        q.push(p.second);
    }

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

        for (auto& p : trie[current].children) {
            int fail = trie[current].failure;
            char trans = p.first;
            int child = p.second;

            while (fail != 0 && trie[fail].children.find(trans) == trie[fail].children.end()) {
                fail = trie[fail].failure;
            }

            if (trie[fail].children.find(trans) != trie[fail].children.end()) {
                fail = trie[fail].children[trans];
            }

            trie[child].failure = fail;
            trie[child].outputs.insert(trie[child].outputs.end(), trie[fail].outputs.begin(), trie[fail].outputs.end());
            q.push(child);
        }
    }

    return trie;
}

int ahoCorasick(const string& text, const vector<string>& patterns) {
    vector<TrieNode> trie = buildTrie(patterns);
    int state = 0;
    int totalMatches = 0;

    for (char c : text) {
        while (state != 0 && trie[state].children.find(c) == trie[state].children.end()) {
            state = trie[state].failure;
        }

        if (trie[state].children.find(c) != trie[state].children.end()) {
            state = trie[state].children[c];
        }

        for (int patternIndex : trie[state].outputs) {
            ++totalMatches;
        }
    }

    return totalMatches;
}

int main() {
    string s;
    getline(cin, s);

    int q;
    cin >> q;
    cin.ignore();

    vector<string> patterns(q);
    for (int i = 0; i < q; ++i) {
        getline(cin, patterns[i]); 
    }

    cout << ahoCorasick(s, patterns) << 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: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED