Aho-Corasick 算法科普
Franc0Fernand0 · x · 2026-07-10
文章回顾了 1975 年提出的 **Aho-Corasick 字符串匹配算法**，该算法解决了在文档中重复扫描大量关键词导致无法扩展的问题。 - **核心机制**：将关键词组织成一棵“共享前缀树”，并添加“失败指针”（类似 KMP 算法）作为捷径。匹配失败时直接跳转，避免重复检查。 - **效率优势**：只需对目标文档读取一次，时间复杂度降至 O(n + m + z)（n 为文本长度，m 为关键词总长度，z 为匹配数），搜索时间不再受关键词数量影响。 - **应用场景**：该算法至今仍广泛应用于 `fgrep` 命令、入侵检测系统（IDS）以及 DNA 基因序列搜索工具中。