参考自 OI Wiki - 回文树

回文树

简介

回文树也叫回文自动机（PAM），每个状态表示一个本质不同的回文子串。

与后缀自动机相似，回文树由状态节点，转移边，fail 链和长度 len 四部分组成。一个节点的转移边指向在它首尾同时加上某个字符到达的状态；fail 指向它的最长回文后缀（也与 Border 等价）；len 表示这个节点表示的回文串长度。

这种结构的方便之处还在于，它可以不用像 Manacher 一样在每两个相邻的字符间插入分隔符以转化偶回文，因为回文树有两个初始状态 len=-1 和 len=0，分别表示奇回文和偶回文。具体请见下文。

构造

对于两个根节点，奇根的转移是单个字符所以不可能失配，因此我们不关心它的 fail。偶根的 fail 指向奇根。

下面是一种增量构造回文树的方法：

• 考虑已经构造了前 n-1 个字符的 PAM，现在加入第 n 个字符 x；
• 从 last 指向的节点（即前缀 p-1 的最长回文后缀）开始跳 fail，直到 s_n=s_{n-len-1}，将这个节点记为 p；
• 若 p 有 x 的出边，则 last 直接指向其出边对应的节点，退出；
• 否则新建节点 q，连边 p\overset{x}{\rightarrow}q，并考虑构造 q 的 fail：
  • 继续跳 p 的 fail，直到再一次有 s_n=s_{n-len-1}，这个节点的出边 x 对应的节点即为 q 的 fail。可以证明它一定有 x 的出边；
  • 若不存在 p 的 fail 链上的祖先使 s_n=s_{n-len-1}，则将 q 的 fail 连向偶根，因为它是所有串的后缀、

性质

• 由上述构造可知，每加入一个节点将最多新建一个节点，因此总结点数不大于 |s|，即一个串 s 的本质不同回文子串数不超过 |s|；
• 可以证明跳 fail 的总次数不超过 2|s|，因此构造 s 的 PAM 复杂度为 O(|s|)；
• 由于不需要类似 SAM 地分裂节点，因此 PAM 的节点是按 fail 树的拓扑序插入的。因此统计出现次数等贡献时只需要逆序枚举状态并加到父亲上即可；
• 也可以像 AC 自动机一样在 fail 树的基础上建出 trie 图，有一些奇妙的应用。

题目

Luogu5496 【模板】回文自动机（PAM）

题意

求给定字符串的每个前缀的回文后缀数，强制在线。

题解

即求每个前缀的最长回文后缀所对应节点在 fail 树中的深度。从它的父亲继承即可。

代码

#include <cstdio>
#include <cstring>
const int MAXN=550000;
const int MAXS=26;
struct PAM
{
    struct Node
    {
        int nxt[MAXS], fail;
        int len, sum;
    } st[MAXN];
    int n, m, lst, rt1, rt0;
    char s[MAXN];
    int newNode(int l)
    {
        int x=++m;
        memset(st[x].nxt, 0, sizeof st[x].nxt);
        st[x].fail=0; st[x].len=l; st[x].sum=0;
        return x;
    }
    void init()
    {
        n=m=0; s[0]='#';
        lst=rt1=newNode(-1);
        rt0=newNode(0);
        st[rt0].fail=rt1;
    }
    int get_fail(int p)
    {
        while (p&&s[n]!=s[n-st[p].len-1]) p=st[p].fail;
        return p;
    }
    void extend(char c)
    {
        s[++n]=c;
        int p=get_fail(lst), x=c-'a';
        if (!st[p].nxt[x])
        {
            int q=st[p].nxt[x]=newNode(st[p].len+2);
            int t=get_fail(st[p].fail);
            st[q].fail=t?st[t].nxt[x]:rt0;
            st[q].sum=st[st[q].fail].sum+1;
        }
        lst=st[p].nxt[x];
    }
} pam;
char str[MAXN];
int main()
{
//  freopen("P5496.in", "r", stdin);
//  freopen("P5496.out", "w", stdout);
    scanf("%s", str);
    pam.init();
    for (int i=0, k=0; str[i]; i++)
    {
        str[i]=(str[i]-97+k)%26+97;
        pam.extend(str[i]);
        printf("%d ", k=pam.st[pam.lst].sum);
    }
    putchar('\n');
    return 0;
}

最小回文划分

最小回文划分是指将一个字符串划分成最小数目的回文串的个数。

不难想到一个 O(n^2) 的 DP：设 f(i) 表示 s 的前缀 [1,i] 的最小回文划分，枚举以 i 结尾的子回文串转移。但有没有更好的方法呢？

首先给出一个引理：

字符串 s 的所有回文后缀按长度排序后，可分为 O(\log|s|) 个等差数列。

具体证明看 OI-wiki 上的好了，实在没看懂。。

有了这个引理，事情就好办了一些。我们在 PAM 的每个状态 p 上多维护两个信息：diff_p 等于该状态与其最长回文后缀的长度差，即 len_p-len_{par_p}；slink_p 表示距 p 最近的 par 树上祖先，使得 diff_p\neq diff_{slink_p}。那么 [p,slink_p) 就代表了一段等差数列，而任意一个节点跳 slink 的次数都是 \log 级别的。

要更新 f 数组，还需要维护每个节点 p 到 slink_p 这段等差数列的贡献，记为 g(p)。考虑从 par_p 处转移，发现

• 若 diff_p\neq diff_{par_p}，说明 p 与 par_p 不在一段等差数列上，那么 g(p)=f(i-len_p)；
• 否则，par_p 上次出现的位置为 i-diff_p，我们可以把它上面的整个等差数列继承下来；此外，还多了一个最短的回文串没有表示出来，它的出现位置为 i-(len_{slink_p}+diff_x)，加上它的贡献就可以了。

最后，不断跳 slink 更新即可。