js版得ac自动机算法

AC自动机（Aho-Corasick Automation）是多模式搜索的高效数据结构和搜索算法，可以同时在一段文本中搜索多个模式字符串。以下是一个简单的JavaScript版AC自动机实现的示例：

class TrieNode {
    constructor() {
        this.children = {};
        this.fail = null;
        this.patterns = [];
        this.isWord = false;
    }
}
 
class AhoCorasickAutomata {
    constructor() {
        this.root = new TrieNode();
    }
 
    addWord(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let char = word[i];
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isWord = true;
        node.patterns.push(word);
    }
 
    buildFailureLink() {
        const queue = [];
        for (let key in this.root.children) {
            this.root.children[key].fail = this.root;
            queue.push(this.root.children[key]);
        }
 
        while (queue.length > 0) {
            const node = queue.shift();
            for (let key in node.children) {
                const child = node.children[key];
                queue.push(child);
                let failNode = node.fail;
                while (failNode !== null && !(key in failNode.children)) {
                    failNode = failNode.fail;
                }
                child.fail = (failNode === null) ? this.root : failNode.children[key];
                if (child.fail.isWord) {
                    child.patterns.push(...child.fail.patterns);
                }
            }
        }
    }
 
    search(text) {
        let node = this.root;
        let results = [];
        for (let i = 0; i < text.length; i++) {
            while (node.children[text[i]] === undefined && node !== this.root) {
                node = node.fail;
            }
            node = node.children[text[i]] || this.root;
            let temp = node;
            while (temp !== this.root && temp.patterns.length > 0) {
                results.push(...temp.patterns.map(pattern => ({ pattern, start: i - pattern.length + 1, end: i })));
                temp = temp.fail;
            }
        }
        return results;
    }
}
 
// 使用示例
const acAutomata = new AhoCorasickAutomata();
acAutomata.addWord('apple');