PAM 学习笔记

定义

PAM (Palindrome Automaton) 是一种处理回文串的、针对某个串的自动机，它保存了该串所有回文串的信息。

PAM 需要维护三个基础的东西：点、转移边、fail 边。PAM 和 AC 自动机类似，所以我们可以借鉴 AC 自动机来理解这些东西。

	AC 自动机	PAM
点	一个前缀	一个回文串
转移边	从起点走到终点，相当于在起点的字符串后面加上一个字符	从起点走到终点，相当于在起点的字符串两侧都加上一个字符
fail 边	存在的最长后缀	存在的最长回文后缀

但是，PAM 有一个 AC 自动机不具有的性质——它有两个根！因为可以发现走转移边并不会改变回文串长度的奇偶性，这样的话就保存不了所有的回文串了，所以我们需要两个根，一个叫做奇根，还有一个叫做偶根，这样才能维护所有的回文串。

构造

定义完了那就看看怎么构造它。这里我们使用增量法。

为了方便，我们给每个点定义一个结构体，存当前点的信息，这里我们就维护三个信息：当前回文串的长度、转移边、fail 边。

struct Node {
  int len;
  int son[26], fail;
} t[MAXN];

先看看怎么初始化，显然我们要先定义两个根。对于奇根，它的长度为 -1 （可以把在它两侧加一个字符，当做它会吃掉一个字符），它一开始没有儿子，它的 fail 边随便指（因为它的两侧一定可以加字符）。对于偶根，它的长度为 0 （可以看成是空串），它一开始没有儿子，它的 fail 边指向奇根，因为它两侧不能加字符的话，就只能丢给奇根了。即：（0 号节点是偶根，1 号节点是奇根）

1 2	t[0].len = 0; t[1].len = -1; t[1].fail = t[0].fail = 1;

假设上一次加入的点是 last ，现在需要新增一个字符 ch，假设它存储在 s[pos]。

首先我们需要找到一个 last 所代表串的一个最长后缀，使得可以在这个后缀后面加上 ch，即

int Getfail(int last, int pos) {
  while (s[pos] != s[pos - t[last].len - 1])
    last = t[last].fail;
  return last;
}

我们把这个最长后缀所在的点记作 cur，然后接下来就看 cur 节点有没有 ch 这个儿子，如果有就直接跳过，把 last 设为这个儿子，否则就新增一个节点，记为 nxt。

对于 nxt，它的长度是 cur 的长度 +2 （根据转移边的定义）。它的 fail 的寻找和 AC 自动机很像，是在 cur 的 fail 中再找到一个最长的有 ch 这个字符的儿子的后缀，然后把 nxt 的 fail 指向那个后缀的 ch 儿子。最后再把 cur 的 ch 儿子设为 nxt。具体实现如下。

int nxt = ++cnt;
t[nxt].len = t[cur].len + 2;
t[nxt].fail = t[Getfail(t[cur].fail, pos)].son[s[pos] - 'a'];
t[cur].son[s[pos] - 'a'] = nxt;

最后也需要让 last 等于 nxt 。

这样就可以把 PAM 构造出来，复杂度是 \(O(n)\) 的，因为每次跳 fail 会让当前串的长度至少减 2，而加入一个字符只会让当前串的长度加 2，所以跳 fail 的次数是有保障的。

应用

PAM 可以处理很多有关回文串的信息，具体在此就不展开了。实际上我们可以把 AC 自动机或是 SAM 的那些套路拿到 PAM 上来用，具体的怎么做还是得要进行实践。