Ахо-Корасик

1function ahoCorasick(text: string, patterns: string[]): Array<[string, number]> {
2  // 1. Trie из образцов; 2. fail-ссылки BFS; 3. один проход по тексту
3  const root = buildTrie(patterns)
4  linkFails(root)
5 
6  const hits: Array<[string, number]> = []
7  let node = root
8  for (let i = 0; i < text.length; i++) {
9    while (node !== root && !node.children.has(text[i]!)) node = node.fail!
10    node = node.children.get(text[i]!) ?? root
11    for (const word of output(node)) {
12      hits.push([word, i - word.length + 1])
13    }
14  }
15 
16  return hits
17}