PAM

回文自动机是能够存储所有回文子串的数据结构，下面是几个概念：

  1. 节点：每一个节点代表一种回文串，下面用 SuS_u 表示节点 uu 代表的回文子串。
  2. 后继边：每个后继边上有一个字母，若 v=trans(u,ch)v=\text{trans}(u,\texttt{ch}) 表示 Sv=chSuchS_v=\texttt{ch} S_u\texttt{ch}，那么 ∣Sv∣=∣Su∣+2|S_v|=|S_u|+2。
  3. 失配边：每个节点都有失配边，若 v=fail(u)v=\text{fail}(u) 表示 SvS_v 是 SuS_u 的最大回文后缀。

由于长度为奇数的回文串与长度为偶数的回文串情况不仅相同，所以在 PAM 中有两个根节点 0,10,1 分别表示空的长度为奇数、偶数的串，并且令 fail(0)=1,fail(1)=0\text{fail}(0)=1,\text{fail}(1)=0，下文中我们通过构建过程来说明这是为什么。

首先给出一个初始化的函数，这里 tot 表示字符的数量，idx 表示节点的数量，last 表示上一次操作后插入的字符对应的节点并且初始值为 00，len[u] 表示 ∣Su∣|S_u|。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int tot, idx, last;
int fail[N], tr[N][26], len[N];
char s[N];

int create(int l) {
    idx++;
    memset(tr[idx], 0, sizeof tr[idx]);
    len[idx] = l;
    fail[idx] = 0;
    return idx;
}

void init() {
    idx = -1;
    tot = 0;
    s[0] = '$';
    last = 0;
    create(0);
    create(-1);
    fail[0] = 1;
}

当我们插入一个新的字符 ch\texttt{ch} 时，先将 ch\texttt{ch} 加到 PAM 中保存的 ss 的末尾，令 now=lastnow=last，尝试通过 trans(now,ch)\text{trans}(now, \texttt{ch}) 边，如果不行就 now←fail(now)now\gets \text{fail}(now)，一直跳到行为止。

为什么？因为以当前位置结尾的回文串，扣掉最后一个位置和第一个位置后，前面一定也是一个回文子串，所以我们从前一个位置结尾的最长回文子串开始转移是合适的。

如果转移合法，表示当前串结尾是 chSnowch\text{ch}S_{now}\text{ch}，我们只需检查 stot−∣Snow∣−1s_{tot-|S_{now}|-1} 是否等于 stots_{tot} 即可。

然后，当前节点的失配指针就尝试从 fail(now)\text{fail}(now) 向下添加即可，所以我们可以定义一个 getfail 函数辅助我们跳 fail\text{fail} 链。

当所有尝试都失败时，我们面临向空串插入一个字符的情境，这仍然会有两种可能性：

  1. 以 chch\texttt{ch}\texttt{ch} 的形式，此时它应当满足 stot−1=stots_{tot-1}=s_{tot}，从根节点 00 转移过来，失配指针指向 00。
  2. 以 ch\texttt{ch} 的形式，此时它应当满足 stot=stots_{tot}=s_{tot}，从根节点 11 转移过来，失配指针指向 00。

为什么失配指针都指向 00？因为我们要先检查能不能凑成长度为 22 的串，容易检查我们让 0,10,1 的失配指针互相指就可以达成这个目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getfail(int x) {
    while (s[tot - 1 - len[x]] != s[tot]) x = fail[x];
    return x;
}

int insert(char ch) {
    s[++tot] = ch;
    int now = getfail(last);
    int p = ch - 'a';
    if (!tr[now][p]) {
        int x = create(len[now] + 2);
        fail[x] = tr[getfail(fail[now])][p];
        tr[now][p] = x;
    }
    return last = tr[now][p];
}

复杂度仍然可通过势能分析，设势能为当前 fail\text{fail} 链的长度，每跳一步 fail\text{fail} 链会让势能减 11，插入一个字符后势能加 11，所以复杂度仍然为线性。

[APIO2014] 回文串

我们可以对每一个位置考虑，以这个位置结尾的回文子串都出现在它的 fail\text{fail} 链上，所以相当于每个节点会给它的整个 fail\text{fail} 链加一。

每次插入的时候给 lastlast 加一，最后进行一遍 DFS 即可。

由于 PAM 是在线的数据结构，每一个节点的 fail\text{fail} 编号一定比它本身的编号要小，所以我们直接按照节点编号从大到小遍历，就可以正确的更新答案。

注意，ACAM 并没有这个性质，因为在 ACAM 中是把所有字典串都插入完，再设置的失配指针，所以这个失配指针指向的节点编号并不一定比当前节点编号小。

AC Code。

[2019徐州网络赛] Colorful String

每一个节点用一个二进制数表示 2626 个字母的状态，最后用 popcount\text{popcount} 求每个节点对应的种类数，乘上对应的出现次数累加即可。

AC Code。

[CCPC2023 秦皇岛] Palindrome

我们把每次询问的子串称为 SS，我们下面讨论基于 SS 不是一个回文串。

由于我们可以删除一个区间 S[l,r]S[l,r] 使剩下的部分 S[1,l−1]+S[r+1,∣S∣]S[1,l-1]+S[r+1,|S|] 是回文串，于是分两种情况讨论。

  1. 如果 l=1l=1 或者 r=∣S∣r=|S|，即删除的是一段前缀/后缀，需要保证剩余的部分是一个回文子串。
  2. 否则，没删除的前后缀需要对应相等。

不妨设删除的部分是在前半段，最后会说怎么处理后半段。

这就启发我们思考，这个前后缀对应相等的长度，是不是越长越好？接下来尝试证明：如果当前删除的区间是 S[l,r]S[l,r]，并且有 Sl=S∣S∣−l+1S_l=S_{|S|-l+1}，那么我们把 l,rl,r 向右平移一个位置，容易验证剩下的部分仍然是一个回文串。

于是我们可以断定，使得前后缀对应相等的长度尽可能长，答案一定不会更劣，所以我们先二分找到一个最大长度。

把这个前后缀扔掉，求删除的最小长度等价于求最长的回文后缀，这可以通过 PAM 上倍增跳 fail\text{fail} 实现。

接下来考虑方案数。由上文的论述，我们不可能再把 l,rl,r 向右移动，于是只能尝试向左移动。如果这个窗口可以移动，意味着移动后释放出来的那个字符等于吃进去的那个字符，所以这里也可以二分。

如果删除的部分是后半段，把整个字符串翻转过来即可，最后比较翻转前后求出来的答案以及方案数，如果答案相等方案数相加即可。

这不可能会重复，因为扔掉对应相等的前后缀后，求得的最长回文后缀长度至少为 11，也就是翻转前删除的部分一定不包含最后一个字符，而翻转后删除的部分一定会包含这个字符，于是它们是不会重复的。

AC Code。