Return to Question

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);
```

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);

class Dequeue {
  front;

  end;

  data = [];

  push(number) {
    if (!this.front) {
      this.front = this.data.length;
      this.end = this.data.length;
      this.data[this.front] = number;
      this.data[this.end] = number;
    } else {
      this.front = this.data.length;
      this.data[this.front] = number;
    }
  }

  shift(number) {
    const value = this.data[this.front];

    delete this.data[this.front];

    this.data.length = this.data.length - 1;

    this.front = this.front - 1;
    if (this.data.length === 0) {
      this.front = undefined;
      this.back = undefined;
    }
    return value;
  }

  display() {
    console.log(this.data, this.data.length);
  }
}

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);
```

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);
```

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);
```

EDIT: Dequeu was the correct guess

class Dequeue {
  front;

  end;

  data = [];

  push(number) {
    if (!this.front) {
      this.front = this.data.length;
      this.end = this.data.length;
      this.data[this.front] = number;
      this.data[this.end] = number;
    } else {
      this.front = this.data.length;
      this.data[this.front] = number;
    }
  }

  shift(number) {
    const value = this.data[this.front];

    delete this.data[this.front];

    this.data.length = this.data.length - 1;

    this.front = this.front - 1;
    if (this.data.length === 0) {
      this.front = undefined;
      this.back = undefined;
    }
    return value;
  }

  display() {
    console.log(this.data, this.data.length);
  }
}

const ROOT_TREE = 0;
const ALPHABET_SIZE = 26;

class TreeNode {
  next;

  isLeaf = false;

  character = '$';

  parentNode = -1;

  outputLink = -1;

  health = [];

  link = -1;

  constructor(p = -1, character = '$') {
    this.parentNode = p;
    this.character = character;
    this.next = new Array(ALPHABET_SIZE).fill(-1);
  }
}

class AhoCorasick {
  trie = [new TreeNode()];

  addString(word, health, index) {
    let treeIndex = 0;
    for (let index = 0; index < word.length; index += 1) {
      const character = word[index];
      const char = character.charCodeAt(0) - 'a'.charCodeAt(0);

      if (this.trie[treeIndex].next[char] === -1) {
        this.trie[treeIndex].next[char] = this.trie.length;
        this.trie.push(new TreeNode(treeIndex, character));
      }
      treeIndex = this.trie[treeIndex].next[char];
    }
    this.trie[treeIndex].health.push({ health, index });
    this.trie[treeIndex].isLeaf = true;
  }


  createLink() { // <===== THIS IS THE SLOW ONE, any advice on this will be appreciate
    const queue = [];
    const treeIndex = 0;

    queue.push(treeIndex);

    while (queue.length > 0) {
      const trieToCheck = this.trie[queue.shift()];
      const nodeToCheck = trieToCheck.next.filter((i) => i !== -1);

      nodeToCheck.forEach((nextIndex) => {
        let childNode = trieToCheck;

        queue.push(nextIndex);
        if (childNode.link !== -1) {
          childNode = this.trie[childNode.link];
        }
        /*const index = childNode.next.find( <== old way of finding index
          (next) =>
            next !== -1 &&
            next !== nextIndex &&
            this.trie[next].character === this.trie[nextIndex].character,
        );*/

        let index; // <=== EDIT: new index calculation

        index =
          childNode.next[
            this.trie[nextIndex].character.charCodeAt(0) - 'a'.charCodeAt(0)
          ];

        if (index === nextIndex) {
          index = null;
        }

        if (!index) {
          this.trie[nextIndex].link = treeIndex;
        } else {
          this.trie[nextIndex].link = index;
          if (this.trie[index].isLeaf) {
            this.trie[nextIndex].outputLink = index;
          } else if (this.trie[index].outputLink !== -1) {
            this.trie[nextIndex].outputLink = this.trie[index].outputLink;
          }
        }
      });
    }
  }

  constructor(words, health) {
    console.time('words');
    words.forEach((word, index) => this.addString(word, health[index], index));
    console.timeEnd('words');
    console.time('link');
    this.createLink();
    console.timeEnd('link');
  }

  processOutputLink(outputLink, health, first, last) {
    if (outputLink === -1) {
      return health;
    }
    const newHealth = this.trie[outputLink].health
      .filter((e) => e.index >= first && e.index <= last)
      .reduce((acc, e) => acc + e.health, 0);

    return this.processOutputLink(
      this.trie[outputLink].outputLink,
      health + newHealth,
    );
  }

  processLink(link, character) {
    if (link !== -1 && this.trie[link].next[character] === -1) {
      return this.processLink(this.trie[link].link, character);
    }
    if (link !== -1 && this.trie[link].next[character] !== -1) {
      return this.trie[link].next[character];
    }

    return link === -1 ? ROOT_TREE : link;
  }

  processNode(index, health, first, last) {
    const node = this.trie[index];
    let newHealth = health;

    if (node.isLeaf) {
      const healthCalc = node.health
        .filter((e) => e.index >= first && e.index <= last)
        .reduce((acc, e) => acc + e.health, 0);

      newHealth += healthCalc;
    }

    newHealth = this.processOutputLink(node.outputLink, newHealth, first, last); // FINITO
    return newHealth;
  }

  getHealth(word, first, last) {
    let health = 0;
    let index = 0;

    for (const c of word) {
      const character = c.charCodeAt(0) - 97;
      const parentNode = this.trie[index];
      const nextIndex = this.trie[index].next[character];

      if (nextIndex !== -1) {
        health = this.processNode(nextIndex, health, first, last);
        index = nextIndex;
      } else {
        const indexSuffix = this.processLink(parentNode.link, character);
        const indexNextNode =
          indexSuffix !== ROOT_TREE
            ? indexSuffix
            : this.trie[indexSuffix].next[character];

        if (indexNextNode !== -1) {
          health = this.processNode(indexNextNode, health, first, last);
          index = indexNextNode;
        } else {
          index = ROOT_TREE;
        }
      }
    }
    return health;
  }
}

const algo = new AhoCorasick(['a', 'aa', 'b', 'bca', 'd'], [5, 10, 15, 20, 25, 30]);

algo.getHealth("aabcaccdabaa", 0, 5);
```