Реализация алгоритма aho corasick — медленное построение суффикса

РЕДАКТИРОВАТЬ: Dequeu был правильным предположением

РЕДАКТИРОВАТЬ: я использовал метод BFS для построения суффиксной ссылки/выходной ссылки.

Я делаю вызов hackerrank, и я придумал эту реализацию алгоритма aho corasick. Все работает нормально, но моя конструкция суффикса слишком медленная, и на ее создание со 100 000 входных данных уходит много времени (построение дерева выполняется довольно быстро, чем 1 с ~ для 100 000 входных данных, но 3 минуты для построения суффикса).

Что я должен сделать, чтобы улучшить мою функцию createLink?

В конце я поместил простой тест, чтобы показать, как его использовать, функция getHealth запускает алгоритм и принимает строку в качестве первого параметра и два числа, которые нужны только для части входных данных.

Допустим, у вас есть:

inputs = ['a', 'b', 'c', 'd']
health = [1, 2, 3, 4]

если вы делаете getHealth с этим:

getHealth('aadbancjlav', 0, 2); // inputs.slice(0, 2 + 1) (+1 because it's exclusive)

Алгоритм пропустит букву «d» и соответствующее ему здоровье.

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.triehttps://codereview.stackexchange.com/questions/281499/implementation-of-aho-corasick-algorithm-slow-suffix-construction.next[character] === -1) {
      return this.processLink(this.triehttps://codereview.stackexchange.com/questions/281499/implementation-of-aho-corasick-algorithm-slow-suffix-construction.link, character);
    }
    if (link !== -1 && this.triehttps://codereview.stackexchange.com/questions/281499/implementation-of-aho-corasick-algorithm-slow-suffix-construction.next[character] !== -1) {
      return this.triehttps://codereview.stackexchange.com/questions/281499/implementation-of-aho-corasick-algorithm-slow-suffix-construction.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);

queue.shift()

вбегает линейное время. Ты нуждаешься в следовательно структура данных для эффективного удаления первого элемента за постоянное время.