AC自动机算法 在计算机科学中艾侯科拉希克算法英語AhoCorasick algorithm是由阿尔佛雷德艾侯和玛格丽特J科拉希克Margaret J Corasick发明的字符串搜索算法用于在输入的一串字符串中匹配有限组字典中的子串它与普通字符串匹配的不同点在于同时与所有字典串进行匹配算法均摊情况下具有近似于线性的时间复杂度约为字符串的长度加所有匹配的数量然而由于需要找到所有匹配数如果每个子串互相匹配如字典为aaaaaaaaaa输入的字符串为aaaa算法的时间复杂度会近似于匹配的二次函数 该算法主要依靠构造一个有限状态机类似于在一个trie树中添加失配指针来实现这些额外的失配指针允许在查找字符串失败时进行回退例如设Trie树的单词cat匹配失败但是在Trie树中存在另一个单词cart失配指针就会指向前缀ca转向某前缀的其他分支免于重复匹配前缀提高算法效率 当一个字典串集合是已知的例如一个计算机病毒库 就可以以离线方式先将自动机求出并储存以供日后使用在这种情况下算法的时间复杂度为输入字符串长度和匹配数量之和 UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的