1
var StreamChecker = function (words) {
2
  function Trie() {
3
    this.suffixLink = null; //this is where it will fallback to when a letter can't be matched
4
    this.id = -1; //this id will be 0 or greater if it matches a word
5
    this.next = new Map(); //map of <char, Trie*>
6
  }
7
  this.root = new Trie();
8
  this.uniqueIds = 0; //used to count all the unique words discovered and as part of the Trie id system
9

10
  //standard trie traversal but keeping track of new words via id system
11
  for (const word of words) {
12
    let ptr = this.root;
13
    for (const c of word) {
14
      if (!ptr.next.has(c)) {
15
        ptr.next.set(c, new Trie());
16
      }
17
      ptr = ptr.next.get(c);
18
    }
19
    if (ptr.id === -1) {
20
      ptr.id = this.uniqueIds++;
21
    }
22
  }
23

24
  //BFS traversal to build the automaton
25
  const q = [];
26
  for (const [c, node] of this.root.next) {
27
    //all first level children should point back to the root when a match to a character fails
28
    node.suffixLink = this.root;
29
    q.push(node);
30
  }
31

32
  while (q.length) {
33
    const curr = q.shift();
34
    for (const [c, node] of curr.next) {
35
      let ptr = curr.suffixLink;
36
      while (ptr !== this.root && !ptr.next.has(c)) {
37
        ptr = ptr.suffixLink;
38
      }
39
      //find the next suffixLink if it matches the current character or fallback to the root
40
      node.suffixLink = ptr.next.get(c) ?? this.root;
41

42
      //if the current suffixLink happens to also be a word we should store its id to make it quick to find
43
      if (node.suffixLink.id !== -1) {
44
        node.id = node.suffixLink.id;
45
      }
46
      q.push(node);
47
    }
48
  }
49
  //the query ptr will now track every new streamed character and use it to match
50
  this.queryPtr = this.root;
51
};
52

53
StreamChecker.prototype.query = function (letter) {
54
  //the query ptr will now track every new streamed character and can be used to quickly find words
55
  while (this.queryPtr !== this.root && !this.queryPtr.next.has(letter)) {
56
    this.queryPtr = this.queryPtr.suffixLink;
57
  }
58
  this.queryPtr = this.queryPtr.next.get(letter) ?? this.root;
59
  //if any word is found it will have an id that isn't -1
60
  return this.queryPtr.id !== -1;
61
};