一名蒟蒻向您问好。

这是 AC自动机，不是自动AC机， 是一个十分常用的多模式字符串匹配算法 （也就是一个主串跟很多串匹配，叫多模式串匹配，那些串就叫模式串）

AC自动机是建立在Trie树上的，它利用fail失配指针（叫别的也一样），来寻找一个其它模式串的前缀与当前模式串的后缀相等。 （比起后缀自动机没有就自己建一条的直接而言，AC自动机这样指针索引的方式似乎更委婉（但后缀自动机的难度似乎更加“委婉”呢（微笑脸））

也就是说，AC自动机是一个魔改的Trie树（或者说加料），其思想和KMP算法的前后缀匹配不谋而合，不过一个在树上，一个在序列里。

虽然我们要讲的是树上的，但为了理解思想，我们用比较好理解的字符串来看，虽然只是一个储存结构的问题。

例如我们有：