1
class StreamChecker {
2
  struct Trie {
3
    Trie *suffixLink; // this is where it will fallback to when a letter can't
4
                      // be matched
5
    int id = -1;      // this id will be 0 or greater if it matches a word
6
    map<char, Trie *> next;
7
  };
8

9
 public:
10
  Trie *root;
11
  Trie *queryPtr;
12
  int uniqueIds = 0; // used to count all the unique words discovered and as
13
                     // part of the Trie id system
14

15
  StreamChecker(vector<string> &words) {
16
    root = new Trie();
17

18
    // standard trie traversal but keeping track of new words via id system
19
    for (string &word : words) {
20
      Trie *p = root;
21
      for (char c : word) {
22
        if (p->next.find(c) == p->next.end()) {
23
          p->next.insert({c, new Trie()});
24
        }
25
        p = p->next.at(c);
26
      }
27
      if (p->id == -1) {
28
        p->id = uniqueIds++;
29
      }
30
    }
31

32
    queue<Trie *> q;
33
    for (pair<char, Trie *> itr : root->next) {
34
      q.push(itr.second);
35
      itr.second->suffixLink = root;
36
    }
37

38
    // BFS traversal to build the automaton
39
    while (q.size()) {
40
      Trie *curr = q.front();
41
      q.pop();
42
      for (pair<char, Trie *> e : curr->next) {
43
        char c = e.first;
44
        Trie *node = e.second;
45

46
        Trie *ptr = curr->suffixLink;
47
        while (ptr != root && ptr->next.find(c) == ptr->next.end()) {
48
          ptr = ptr->suffixLink;
49
        }
50
        // find the next suffixLink if it matches the current character or
51
        // fallback to the root
52
        node->suffixLink = ptr->next.find(c) != ptr->next.end() ? ptr->next.at(c) : root;
53

54
        // if the current suffixLink happens to also be a word we should store
55
        // its id to make it quick to find
56
        if (node->suffixLink->id != -1) {
57
          node->id = node->suffixLink->id;
58
        }
59
        q.push(node);
60
      }
61
    }
62
    // the query ptr will now track every new streamed character and can be used
63
    // to quickly find words
64
    queryPtr = root;
65
  }
66

67
  bool query(char letter) {
68
    // if the next letter can't be found and we're not at the root, we'll trace
69
    // back until we find the longest suffix that matches
70
    while (queryPtr != root && queryPtr->next.find(letter) == queryPtr->next.end()) {
71
      queryPtr = queryPtr->suffixLink;
72
    }
73
    queryPtr =
74
        queryPtr->next.find(letter) != queryPtr->next.end() ? queryPtr->next.at(letter) : root;
75
    // if any word is found it will have an id that isn't -1
76
    return queryPtr->id != -1;
77
  }
78
};