洛谷P5496 【模板】回文自动机（PAM）题解

题意：

给定一个字符串 $s$。保证每个字符为小写字母。

对于 $s$ 的每个位置，请求出以该位置结尾的回文子串个数。

这个字符串被进行了加密，除了第一个字符，其他字符都需要通过上一个位置的答案来解密。

具体地，若第 $i(i\geq 1)$ 个位置的答案是 $k$，第 $i+1$ 个字符读入时的 $\rm ASCII$ 码为 $c$，则第 $i+1$ 个字符实际的 $\rm ASCII$ 码为 $(c-97+k)\bmod 26+97$。所有字符在加密前后都为小写字母。

输入格式：

一行一个字符串 $s$ 表示被加密后的串。

输出格式：

一行， $|s|$ 个整数。第 $i$ 个整数表示原串以第 $i$ 个字符结尾的回文子串个数。

数据范围：

$1\leq |s|\leq 5\times 10^5$。

本题是回文自动机的模板题。

我看题解区的回文自动机都有两个根，看不懂，就自己写了一种回文自动机。

先考虑奇回文串。可以发现，奇回文串去掉两头的字符，就变成了一个新的回文串（单个字符也算）

于是我们可以建一个类似于 Trie 树的东西

根节点 $0$ 还是表示空串，不过根节点的儿子 $\mathtt{ch[0][c]}$ 表示中间的那个字符是 $c$ 。

除此以外，每个节点 $\mathtt{ch[u][c]}$ 表示在父结点 $u$ 的基础上，两头加上字符 $c$ 的字符串。

那么偶回文串怎么办呢？偶回文串其实可以看作中间的那个字符是 $\varnothing$ 。

于是根节点直接多了一个儿子，我们直接把它记为节点 $1$ ，这样回文自动机就只有一个根了。

方便起见，我们记录以每个节点结尾的最长回文串长 $\tt len$ 。定义 $\mathtt{len[0]}=-1,~\mathtt{len[1]} = 0$ 。

$\tt{fail}$ 数组的构建和 AC 自动机类似，定义为最长回文后缀的结尾节点。

定义 $\mathtt{fail[1]} = 0$ ，其他情况 $\mathtt{fail[u]}=\mathtt{ch[fail[fa(u)][c]}$ 。

这里是因为，$u$ 的最长回文后缀，等于 $fa(u)$ 的最长回文后缀加上字符 $c$

那么我们现在有一个初始有两个节点和 $\mathtt{fail}$ 数组的奇怪数据结构，接下来该干什么呢？

考虑维护一个指针 $p$ ，初始 $p=0$ ，然后依次考虑每个字符 $s_i$ 。

如果 $p$ 指向的节点有 $s_i$ 这个儿子，那么直接往这个儿子走即可，答案就是这个儿子的答案。
否则新建 $s_i$ 这个儿子，它的 $\tt len$ 定义为 $\mathtt{len[p]}+2$ ，

接着我们构建它的失配指针 $\mathtt{fail}$ ，即 $\mathtt{ch[p][s_i]}$ 的最长回文后缀（的结尾节点）。

记一个临时变量 $q\gets p$ ，不停让 $q\gets \mathtt{fail[q]}$ ，

直到 $q$ 表示的字符串两头加上 $s_i$ 后等于 $\mathtt{ch[p][s_i]}$ 表示的字符串

于是 $\mathtt{ch[p][s_i]}$ 的 $\mathtt{fail}$ 即为 $\mathtt{ch[q][s_i]}$ 。

然后令 $p=\mathtt{ch[p][s_i]}$ ，继续考虑 $s_i + 1$ 。

答案统计的话，类似于 AC 自动机统计 Fail 树，直接看代码吧。

分析一下复杂度，每增加一个节点，当前深度增加 $1$ 层

而跳 $\mathtt{fail}$ 每次至少减少 $1$ 层，至多减少【当前深度】层。

故时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

char s[N];
int ans, tot, fail[N], len[N], cnt[N], ch[N][26];
int getfail(int p, int i)
{
    while(s[i - len[p] - 1] != s[i]) p = fail[p];
    return p;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); fail[tot = 1] = 0; len[0] = -1;
    for(int i = 1, p, c; s[i]; i++)
    {
        if(i > 1) s[i] = (s[i] + ans - 97) % 26 + 97;
        c = s[i] - 'a'; p = i > 1 ? getfail(p, i) : 0;
        if(!ch[p][c])
        {
            ch[p][c] = ++tot; len[tot] = len[p] + 2; 
            fail[tot] = p > 0 ? ch[getfail(fail[p], i)][c] : 1;
            cnt[tot] = cnt[fail[tot]] + 1; 
        }
        p = ch[p][c]; ans = cnt[p]; cout << ans << ' ';
    }
    return 0;
}