洛谷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;
}