字符串

byT_Q_X

回文自动机(\(PAM\))

回文自动机\(PAM\)是一个能够识别一个字符串所有的回文子串的自动机，是一个 字符串所有回文子串的信息的高度压缩得到的结果。

回文自动机维护了原串上的所有本质不同的回文串。

回文自动机的结构可以看成是两棵树，一棵的根是奇根 \(odd\)，代表着一个长度为 \(−1\) 的实际上不存在的回文串，存储所有长度为奇数的回文串，一棵的根是偶根 \(even\)，代表着长度为 \(0\) 的回文串，存储所有长度为偶数的回文串。

自动机的每一个转移对应树上的一条边，同时带有一个字符 \(c\)，如果这条边连接 \(u → v\)，那么 \(s_v\) 就是 \(s_u\) 在前后分别加上字符 \(c\) 组成的，\(s_u\) 是 \(u\) 节点维护的回文 串。显然，这样做可以表示出所有的回文子串。 此外，同样对每个节点 \(x\) 连接一条失配边 \(fail[x]\) 指向它对应回文串的最长回文 后缀。那么通过一路条 \(fail\)，可以找到该回文串的所有回文后缀。\(fail\) 边同样组 成一棵近似树的结构。

后缀自动机(SAM)

后缀自动机是一个能识别字符串 s 的所有后缀的最小 \(DFA\)，不理解什么是 \(DFA\) 也没关系，总之就是它满足以下性质：

• \(SAM\) 是一个 \(DAG\)，节点被称为状态，边被称为转移，每个转移上是一个字 母。

• 存在一个初始状态，从初始状态出发能到达任意节点，并且将从初始状态出 发的任意路径上的所有转移的字母写下来就是 \(s\) 的一个子串，\(s\)的每一个子 串均能被这样的路径表示出来。

• 存在若干个终止状态，从初始状态到终止状态的任意路径都是 \(s\) 的一个后 缀，\(s\) 的每一个后缀都可以由这样的方式表示出来。

• \(SAM\) 的状态数、转移数都是线性的。