aho corasick algorithm in javascript

To implement the Aho-Corasick algorithm in JavaScript, we need to follow the below steps:

Define a Trie data structure to store the patterns.
Create a failure function for the Trie to efficiently search for patterns in the input text.
Traverse the input text using the Trie and the failure function and identify the matches.

Here's an implementation of the Aho-Corasick algorithm:


index.tsx
class Trie {
  constructor() {
    this.root = {};
    this.failure = {};
  }

  insert(word) {
    let current = this.root;
    for (let ch of word) {
      if (!(ch in current)) {
        current[ch] = {};
      }
      current = current[ch];
    }
    current.isEnd = true;
  }

  buildFailureFunction() {
    const queue = [];
    for (let ch in this.root) {
      const node = this.root[ch];
      node.failure = this.root;
      queue.push(node);
    }
    while (queue.length) {
      const current = queue.shift();
      for (let ch in current) {
        if (ch === 'failure') continue;
        const node = current[ch];
        let failure = current.failure;
        while (!(ch in failure) && failure !== this.root) {
          failure = failure.failure;
        }
        node.failure = failure[ch] || this.root;
        queue.push(node);
      }
    }
  }

  search(text) {
    let current = this.root;
    const result = [];
    for (let i = 0; i < text.length; i++) {
      let ch = text[i];
      while (!(ch in current) && current !== this.root) {
        current = current.failure;
      }
      current = current[ch] || this.root;
      if (current.isEnd) {
        result.push([i - word.length + 1, i]);
      }
    }
    return result;
  }
}

const trie = new Trie();
trie.insert('he');
trie.insert('she');
trie.insert('his');
trie.insert('hers');
trie.buildFailureFunction();

const text = 'ishershe';
const result = trie.search(text);
console.log(result); // [[2, 5], [3, 5], [4, 5], [7, 10], [8, 10]]

1525 chars
68 lines

In this implementation, we define a Trie class to store the patterns, and use a buildFailureFunction method to create the failure function for the Trie.

Then, we can use the search method to traverse the input text using the Trie and the failure function and identify the matches.

Overall, this implementation provides an efficient solution for string matching with multiple patterns in JavaScript.