AC自动机可以解决多个模式串匹配一个主串的情况，不需要将每个字串用KMP匹配一次，换时间……
首先把模式串建一个Trie图，然后在Trie图里面找当前节点的最长后缀，比KMP多考虑了其他串。
显然Trie树中下面的节点比上面的节点表示的串更长，于是优先考虑同层的，然后向上考虑……
然后可以像KMP那样按照bfs递推了……
图上画了几个失配指针，其实除了根结点的每个节点都有失配指针
失配是指某个节点之后没有对应的节点，这时候沿着失配指针往回走后再判断是否失配
暂坑
原文：https://www.cnblogs.com/sahdsg/p/10930181.html