AC自动机算法是什么

AC自动机算法是字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。

在计算机科学中，Aho–Corasick 算法是由 Alfred V. Aho 和 Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为 a，aa，aaa，aaaa，输入的字符串为 aaaa），算法的时间复杂度会近似于匹配的二次函数。

简介

AC 自动机算法主要依靠构造一个有限状态机（类似于在一个 trie 树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设 Trie 树的单词 cat 匹配失败，但是在 Trie 树中存在另一个单词 cart，失配指针就会指向前缀 ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。

当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用，在这种情况下，算法的时间复杂度为输入字符串长度和匹配数量之和。

UNIX 系统中的一个命令 fgrep 就是以 AC 自动机算法作为基础实现的。