回文自动机小结

之前一直不是很会用 PAM，现在感觉可以稍微写点东西了。

PAM 结构

PAM 虽然是一个自动机，但是绝大多数时候是被当成一个回文树来用的。

PAM 的构造算法证明了一个字符串的本质不同回文子串个数是$O(n)$的。

PAM 上的一个结点就代表一个回文子串。

$fail(u)$指向$u$的最长回文后缀所在的结点。$\ell(u)$表示$u$代表回文串的长度。

那么想必你已经差不多了解 PAM 的结构了。

有关回文串的性质

我们知道 KMP 与 border 和循环节是有很大关系的。

对于回文串$s$，$s$的回文后缀也是它的前缀，即 border。

那么咱们翻一翻字符串导论的那篇博客，不难得出结论：回文后缀也是由$O(\log_2|s|)$个等差数列构成的。

那么根据回文树的结构是可以轻松找出这些等差数列的。

一类回文 DP 问题

假设$s[1, i]$对应的回文树结点为$u$，且$u$的祖先为$S(u)$。那么考虑以下形式的 DP：

$$f(i) = \sum_{v \in S(u)} f(i - \ell(v))$$

比如经典的回文划分计数。

既然已知$S(u)$可划分为$\log$个等差数列，那我们可以优化这个转移。

不妨记$d(u) = \ell(u) - \ell(fail(u))$，表示公差。

这样我们其实可以用$\log$个结点来代替$S(u)$，它们是等差数列的末尾（最长的那个串对应的结点），记作$v_1, \ldots, v_t$。那么转移就可以写成

$$f(i) = \sum_{j = 1}^t \sum_{k = 0}^{\displaystyle \frac{\ell(v_j) - \ell(v_{j - 1})}{d(v_j)} - 1} f(i - \ell(v_j) + kd(v_j))$$

后面那个很丑，但本质上就是枚举$v_i$所在等差数列的所有数。不妨记

$$g(v_j) = \sum_{k = 0}^{\displaystyle \frac{\ell(v_j) - \ell(v_{j - 1})}{d(v_j)} - 1} f(i - \ell(v_j) + kd(v_j))$$

这样我们就可以写出$f(i) = \sum_{j = 1}^t g(v_j)$。

其实我们记$top(u)$表示$u$祖先中第一个不在$u$等差数列中的结点，那么上式可以比较优雅地写成

$$g(u) = \sum_{k = 0}^{\displaystyle \frac{\ell(u) - \ell(top(u))}{d(u)} - 1} f(i - \ell(u) + kd(u))$$

然后我们来思考一下，从$i - 1 \to i$，有哪些$g$的值会发生变化：显然是$u$到根路径上的点。

但是我们在计算$f(i)$的时候需要用到哪些结点的$g$的值：只需要$u$到根路径上等差数列末尾结点。

然后我们再想想，假设$p$是$u$到根路径上某个等差数列末尾结点。那么要计算$g(p)$关于$i$的值我们需要用到哪些结点的值。

为此首先思考$f(i - d(u))$对应的结点是什么：一定是$fail(u)$。这个地方你如果想证明，对着$f(i - d(u))$想可能不太行，不妨思考$fail(u)$对应的回文串在$i$之前最晚出现的位置。然后去$fail(u)$的定义那里推矛盾。

那么我们就可以分析得到：

• 首先如果$fail(p)$与$p$不在同一等差数列（$fail(p) =top(p)$），那么我们可以简单计算$g(p)$关于$i$的值（利用之前的 DP 值）
• 如果$fail(p)$与$p$在同一等差数列，那么我们可以借助$g(fail(p))$关于$i - d(u)$的值。

可以发现，上面的条件是归纳的。只要你能保证你将$u$到根路径上等差数列末尾结点的$g$更新为关于$i$的值，那么之后的更新也是对的。

第二种情况具体如何借助？比较$g(u)$和$g(fail(u))$，可以发现两者只是差了长度最短的回文后缀对应的转移，那么加上即可。实际上这个转移正是第一种情况的转移。所以可以合起来写。

#include "head.h"
const int SZ = 1e6 + 500, ALP = 26;
// 0 号结点表示 0 结点，1 号结点表示 -1 结点，长度为 -1
// las 记录上一次插入的字符所在结点的编号
int tot, las, s[SZ], ls; // 字符串的内容 -'0'
int len[SZ], tr[SZ][ALP], fail[SZ];
// d[u] == len[u] - len[fail[u]]，等差数列公差
// top[u]: u 所在等差数列的开头父亲，第一个 d[u] != d[top[u]] 的结点
int d[SZ], top[SZ];
int newNode(int l) {
  ++tot, len[tot] = l, fail[tot] = 0;
  FOR(i, 0, ALP - 1) tr[tot][i] = 0;
  return tot;
}
int getfail(int u) {
  // 将 u 的 fail 链状态上的状态尝试去用 s[ls] 扩展，返回第一个可扩展结点
  while (s[ls - len[u] - 1] != s[ls]) u = fail[u];
  return u;
}
void insert(int c) { // assert(0 <= c && c < ALP);
  s[++ls] = c;
  int cur = getfail(las);
  if (!tr[cur][c]) { // 如果没有转移就添加
    int u = newNode(len[cur] + 2);
    fail[u] = tr[getfail(fail[cur])][c], tr[cur][c] = u;

    d[u] = len[u] - len[fail[u]]; // assert(d[u] >= d[fail[u]]);
    if (d[u] != d[fail[u]]) top[u] = fail[u];
    else top[u] = top[fail[u]];
  }
  las = tr[cur][c];
}
void init() {
  tot = -1, newNode(0), newNode(-1), fail[0] = 1, las = 0;
  d[0] = d[1] = 0, top[0] = 1;
  s[ls = 0] = -1; // -1 表示非匹配字符
}

const int N = 1e6 + 5, P = 1e9 + 7;
// f: 回文划分方案数
// g[u]: sum f[i - len[v]]，v 是 u 的祖先（含）top[u] 的子孙（不含）
int g[SZ], f[N];
int solve(string str) {
  int n = str.size();
  init();
  f[0] = 1;
  FOR(i, 1, n) {
    insert(str[i - 1] - 'a');
    for (int u = las; u > 1; u = top[u]) {
      g[u] = f[i - len[top[u]] - d[u]] % P;
      if (fail[u] != top[u]) g[u] = (g[u] + g[fail[u]]) % P;
    }
    for (int u = las; u > 1; u = top[u]) f[i] = (f[i] + g[u]) % P;
  }
  return f[n];
}