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');