字符串匹配算法之 AC 自动机

（给算法爱好者加星标，修炼编程内功）来源：司徒正美zhuanlan.zhihu.com/p/80325757我们经常用的字符串方法indexOf，都是判定两个字符串的包含关系，底层使用类似KMP，BM， Sunday这样的算法。如果我们要判断一个长字符串是否包含多个短字符串呢？比如在一篇文章找几个敏感词，在DNA串中找几个指定的基因对pattern进行预处理，如果我们的模式串存在多个，则不适合了，我们就需要用到一种多模式匹配算法。最著名的多模式匹配算法为AC自动机，它是由贝尔实验室的两位研究人员 Alfred V. Aho 和 Margaret J.Corasick 于1975年发明的，几乎与KMP算法同时问世，至今日仍然在模式匹配领域被广泛应用。AC自动机的核心算法仍然是寻找模式串内部规律，达到在每次失配时的高效跳转。这一 ………………………………