Aho–Corasick算法

算法先把有限的一组非空关键词插入前缀树，相同前缀复用同一条路径；到达某个关键词结尾的状态，记录相应输出。这样不必让每个模式各自重新扫描整篇文本。原论文把构造状态机与使用它扫描文本明确分成两步。

模式he、she、his、hers可以共享部分路径。扫描ushers到she结尾时，不仅she命中，它的后缀he也命中，因此一个状态可能对应多个输出，不能只记录“找到某个词”就丢掉其他有效出现。

参考：[1]

当前状态没有所需字符转移时，沿失配联系退到较短状态，继续处理同一个输入字符。失配目标表示当前已读片段的最长真后缀，同时这个后缀也是某个模式的前缀，因此不必把文本位置退回重新开始。

构造可以按前缀树深度广度优先推进，让较短状态的失配信息先可用，并把失配目标的输出纳入当前输出。另一种实现预先补齐确定性转移，以更多表项换取每个字符一次直接转移；两者的内存组织并不相同。

参考：[1]

在固定字母表、转移查询为常数成本，且输出采用共享或输出链接等不逐状态复制全部继承集合的表示、按编号报告命中的实现模型下，可把构造和搜索合计写成O(M+n+z)，M为模式总长度、n为文本长度、z为报告数量。若逐条复制完整关键词，或用线性列表查找大量转移，还须计入额外成本。

原论文已说明同一位置可能产生大量命中，也为图书检索另外加入词边界条件。词典改变需要维护状态机；至于某个常见词在正文中究竟指软件、人物还是普通含义，仍需上下文判断，不能把所有字符命中直接升级为实体关系。

参考：[1]