后缀自动机（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指针。