回文树（EER Tree，Palindromic Tree），有点类似Trie，但它并不是匹配字符串的，很多人称之为回文自动机，但它一点也不像自动机，不过我还是按习惯的来，使用PAM为简称。为了表示一个回文，我们只表示一边的一个单链即可，这时就类似Trie。但不同之处是，回文区分奇数长度和偶数长度，所以这里我们使用两个根，分别来表示奇数长度和偶数长度。所以，在奇数根里，链ba表示aba，而在偶数根里的ba表示abba。
首先我们来直观地看看PAM的图形化，以下是字符串abcbbc的PAM
graph TD; linkStyle default interpolate basis subgraph root 0-.->1[-1] end subgraph node0 0-->6((bb)) 6-->7((cbbc)) end subgraph node1 1-->2((a)) 1-->3((b)) 1-->4((c)) 4-->5((bcb)) end 2-.->0 3-.->0 4-.->0 6-.->3 5-.->3 7-.->4 style 0 fill:#f9f style 1 fill:#f9f 实线方向就是子节点方向，虚线是fail指针，指向这个节点最长的回文后缀节点。图有点乱，但又不希望画得过于简单导致说不清楚，将就一下吧。
后缀自动机（SAM），可以结合前文的AC自动机一起理解，所谓后缀自动机，就是把一个字符串的所有后缀构造AC自动机，即只匹配其后缀的自动机。但是作为一个字符串的所有后缀，与一般的AC自动机有些不一样的性质，直接构造AC自动机，节点数是 $O(n^2)$，而SAM则对重复的节点合并了，可以让节点数大幅下降到 $O(n)$。
首先我们来直观地看看SAM的图形化，以下是字符串abcac的SAM
graph LR; linkStyle default interpolate basis 0((0))--a-->1 1--b-->2 2--c-->3 3--a-->4 4--c-->5((5)) 0--c-->6(1) 0--b-->2 1--c-->5 6--a-->4 4-.->1 5-.->6 3-.->6 1-.->0 2-.->0 6-.->0 style 0 fill:#f9f style 5 fill:#f9f 实线方向就是匹配方向，虚线与AC自动机中的失败指针非常像，在SAM里称为link指针。
听到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