听到AC自动机很多人第一次听到的反应往往是很兴奋的。但其实并不是你们想的那种东西。它的全称是Aho-Corasick algorithm，另外，自动机的英文是Automaton，所以AC自动机即 AC Automaton。为了解释这个算法，首先我们来回顾KMP，你需要很理解KMP的原理，不然看后面的内容就会变得妙不可读。
KMP自动机 本质上KMP其实就是一种自动机。这次我们改用自动机的形式来理解。所谓自动机，一般指的是确定有限状态自动机，你可以看作一个黑箱，每次输入一个数据，它就会改变它的内部状态，并有相应的输出。如果你知道Trie，那么它其实就是一个典型的自动机。我们还是拿字符串abacabab作为例子，如果是生成next数组，结果如下：
string a b a c a b a b \0 next -1 0 0 1 0 1 2 3 2 为了方便变成自动机的方式理解，我们把这个改成有向图
graph LR; linkStyle default interpolate basis 0[Start]--a-->00[1] 00--b-->1[2] 1--a-->2[3] 2--c-->3[4] 3--a-->4[5] 4--b-->5[6] 5--a-->6[7] 6--b-->7[8] 00-.->0 1-.->0 2-.->00 3-.->0 4-.->00 5-.->1 6-.->2 %%7[b]-.->3[c] style 0 fill:#f9f,stroke-dasharray: 5, 5 style 7 fill:#f9f,stroke-dasharray: 5, 5
KMP已经介绍过了，这次主要介绍的是Manacher
最长回文子串 Manacher算法要解决的问题就是求最长回文子串，用到的思维和扩展KMP实在是像，不过理解起来比扩展KMP简单。
先定义数组v，v[i]表示以第i个字符为中心，到回文串一端的距离，我们以字符串"acabacab"为例，如下表（index是下标）
string a c a b a c a b \0 index 0 1 2 3 4 5 6 7 8 m ^ i ^ e ^ v 1 2 1 4 i是当前要计算的指针，m是上次计算的指针，e是下一个要比较的位置的指针
然后++i，注意这时候，由于以字符b两边是对称的，所以在求v[4]的值的时候，可以先查v[2]的值，是1，所以v[4]也是1
string a c a b a c a b \0 index 0 1 2 3 4 5 6 7 8 m ^ i ^ e ^ v 1 2 1 4 1 再继续++i，同样的，在求v[5]的值的时候，可以先查v[1]的值，是2，但是，这个长度达到了e指针的位置，即i+2>=e，这时候就更新指针m，并扩展e的位置，即比较str[7]与str[3]，找到以下标5为中心的回文串边界。
KMP之所以在竞赛中常见，并不是因为它用来匹配字符串，而是用它的next数组，为了介绍它，我们先讲讲最长公共前缀
最长公共前缀 我们拿字符串ababcab作为例子
string a b a b c a b len 0 0 1 2 0 1 2 这里所表达的是，例如取第3、4个字符”ab”，这个子串与前缀完全匹配，且它的长度是2，所以就记录2，而第3、4、5个字符”abc”与前缀不能完全匹配，就记作0，含义就这么简单，而且你会发现，计算b的时候，可以根据它所匹配的字符的偏移来，b如果是匹配的，就找到匹配的那个字符是数组中的第几个，它是第二个，所以填2进去。我们再来看更复杂的例子
string a b a c a b a b len 0 0 1 0 1 2 3 2 最后那个字符不匹配的时候，1是怎么计算出来的呢，直接重新计算当然也可以，但就出现重复计算了。我们考虑一下匹配过程，在前面的字符a的时候，前后各一个指针，像这样
string a b a c a b a b len 0 0 1 0 1 2 3 ? pointer ^ ^ 然后两个a匹配，arr[6] = pointer1 - arr 得到3，然后两指针一起移动
string a b a c a b a b len 0 0 1 0 1 2 3 ? pointer * ^ ^ 这时候，不匹配，那么前一个指针上一次指向的是arr[2]的位置，即图上*的地方，值是1，这个值如果是p，那就移动到arr[p]的地方，所以就移动到arr[1]的地方，本质上就是找到前一个匹配此后缀的位置，即
string a b a c a b a b len 0 0 1 0 1 2 3 2 pointer ^ ^ 然后再尝试匹配，这次匹配上了，然后前一指针指向第二个元素，所以赋值2