Buzzwords

#include <bits/stdc++.h>
using namespace std;

const int ALPHABET_SIZE = 27;

int charToIndex(char c) {
    if (c == ' ') return 26;
    return c - 'a';
}

struct Node {
    int children[ALPHABET_SIZE];
    int fail;
    vector<int> output;
    Node() : fail(0) {
        for(int i=0;i<ALPHABET_SIZE;i++) children[i] = -1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    getline(cin, s);
    
    int q;
    cin >> q;
    cin.ignore();
    
    vector<Node> trie;
    trie.emplace_back();
    
    vector<int> counts(q, 0);
    
    for(int i=0;i<q;i++){
        string pattern;
        getline(cin, pattern);
        int node = 0;
        for(char c: pattern){
            int idx = charToIndex(c);
            if(trie[node].children[idx] == -1){
                trie[node].children[idx] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].children[idx];
        }
        trie[node].output.push_back(i);
    }
    
    queue<int> qNodes;
    for(int i=0;i<ALPHABET_SIZE;i++){
        if(trie[0].children[i] != -1){
            trie[trie[0].children[i]].fail = 0;
            qNodes.push(trie[0].children[i]);
        }
        else{
            trie[0].children[i] = 0;
        }
    }
    
    while(!qNodes.empty()){
        int current = qNodes.front();
        qNodes.pop();
        for(int i=0;i<ALPHABET_SIZE;i++){
            if(trie[current].children[i] != -1){
                int child = trie[current].children[i];
                int fail = trie[current].fail;
                while(trie[fail].children[i] == -1 && fail != 0){
                    fail = trie[fail].fail;
                }
                if(trie[fail].children[i] != -1){
                    fail = trie[fail].children[i];
                }
                trie[child].fail = fail;
                for(auto pid: trie[fail].output){
                    trie[child].output.push_back(pid);
                }
                qNodes.push(child);
            }
            else{
                trie[current].children[i] = trie[trie[current].fail].children[i];
            }
        }
    }
    
    int node = 0;
    for(char c: s){
        int idx = charToIndex(c);
        while(trie[node].children[idx] == -1 && node != 0){
            node = trie[node].fail;
        }
        if(trie[node].children[idx] != -1){
            node = trie[node].children[idx];
        }
        else{
            node = 0;
        }
        for(auto pid: trie[node].output){
            counts[pid]++;
        }
    }
    
    long long total = 0;
    for(auto cnt: counts){
        total += cnt;
    }
    cout << total;
}

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