个人比较推荐的回文自动机学习路径：

回文自动机学习博客：
回文树（讲的最严谨，oiwiki上的）
回文自动机（Palindrome Automanton PAM）（讲的最通俗易懂，知乎上的）
回文自动机（PAM）学习笔记（代码最简洁，洛谷上的）

例题：

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

题目背景

模板题，无背景（其实是我想不出背景）。

题目描述

给定一个字符串 $s$。保证每个字符为小写字母。对于 $s$ 的每个位置，请求出以该位置结尾的回文子串个数。

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

debber

样例输出 #1

1 1 1 2 1 1

样例 #2

样例输入 #2

lwk

样例输出 #2

1 1 2

样例 #3

样例输入 #3

lxl

样例输出 #3

1 1 1

提示

对于 $100\%$ 的数据， 1 ≤ ∣ s ∣ ≤ 5 × 1 0 5 1\\leq |s|\\leq 5\\times 10^5 1≤∣s∣≤5×105。

思路：

PAM模板题

时间复杂度：$O(n)$

构造思路 + 代码 + 注释：

回文自动机构造采用增量法，枚举每一个位置 i，处理 i 的后缀。

假设已经构建好 s[0 ~ i - 1] 的回文树，当添加 s[i] 时，如何增量构建？
对于 i 后缀的回文子串，它包含了 i - 1 的回文子串。一个朴素的想法是：得到了 i - 1 后缀的所有回文子串，就能从大到小枚举，判断能否首尾加入字符 s[i] 得到更长的回文串。
但是这样每个位置可能要存很多回文子串，这样是不行的。
事实上，我们只需保存每个回文串的最大回文后缀（不含自己），即失配指针，就能够通过失配指针遍历 i - 1 的所有回文后缀。
节点 u 代表回文串的最大回文后缀（不含自己）的节点位置为 fa[u]，
节点 u 代表的回文串的长度为 len[u]。

如果要得到 i 的最长和次长回文后缀。可以通过如下办法：
找到 i - 1 的最大回文后缀，判断可不可以增长
如果不可以，令 u = i - 1
判断 i - 1 的次长回文后缀 fa[u] 可不可以增长
如果不可以，则让 u = fa[u]，然后继续上一步，直到 u 为空

#include<bits/stdc++.h>using namespace std;const int N = 5e5 + 10;
//lstp：每次刚开始插入字符 s[i] 时，表示的是 s[i - 1] 后缀的最大回文子串节点
//tot：最新创建节点编号
//fa：fa[u] 表示 u 节点代表的回文串的最大回文后缀（不含自己）的节点位置
//len：len[u] 为节点 u 代表的回文串的长度
//cnt：每个节点代表子串的出现次数
//ch：转移边
int lstp, tot, fa[N], len[N], cnt[N], ch[N][26];
char s[N];inline void init()
{lstp = 0, tot = 1;	//初始已存在奇偶两根，tot 初始化为 1fa[0] = 1, fa[1] = len[0] = 0, len[1] = -1;
}int getfa(int p, int idx) 
{//检查 s[i - len[p] - 1] 是否等于 s[i]while (idx - len[p] - 1 < 0 || s[idx - len[p] - 1] != s[idx]) {//不等于，则令 p = fa[p] 重复上面的检查，直到满足。p = fa[p];}//如果等于，得到了以 s[i] 结尾的最长回文串，返回所在节点return p;
}void insert(int c, int idx) //增量构建PAM，和SAM类似
{//先通过 getfa 找出以 s[i] 结尾的最长回文串所在节点 pint p = getfa(lstp, idx);//找到这个 p 以后，检查 ch[p][s[i]] 是否存在//如果不存在if (!ch[p][c]) { int np = ++tot;	//在 trie 树中创建并加入一个新节点 np//更新 faint v = getfa(fa[p], idx);	//先找到 p 后缀中最长的回文后缀，且满足前一个字符是 s[i] 的后缀对应节点 vfa[np] = ch[v][c];	//将 fa[np] 指向 v 的儿子 ch[v][s[i]]，因为它就是当前后缀 s[1, i] 最长的回文后缀//更新 lenlen[np] = len[p] + 2;	//首尾加//根据题意，更新 cntcnt[np] = cnt[fa[np]] + 1;ch[p][c] = np;}//如果存在，说明之前已经处理过了。无需处理，只需根据需求更新一些必要统计信息lstp = ch[p][c];
}signed main() 
{scanf("%s", s);init();int last = 0;for (int i = 0; s[i]; ++i) {if (i)	s[i] = (s[i] - 'a' + last) % 26 + 'a';	//强制在线insert(s[i] - 'a', i);last = cnt[lstp];printf("%d ", last);}puts("");return 0;
}

空白代码

#include<bits/stdc++.h>using namespace std;const int N = 5e5 + 10;
int lstp, tot, fa[N], len[N], cnt[N], ch[N][26];
char s[N];inline void init()
{lstp = 0, tot = 1;	fa[0] = 1, fa[1] = len[0] = 0, len[1] = -1;
}int getfa(int p, int idx)
{while (idx - len[p] - 1 < 0 || s[idx - len[p] - 1] != s[idx]) {p = fa[p];}return p;
}void insert(int c, int idx) 
{int p = getfa(lstp, idx);if (!ch[p][c]) {int np = ++tot;	int v = getfa(fa[p], idx);	fa[np] = ch[v][c];	len[np] = len[p] + 2;	cnt[np] = cnt[fa[np]] + 1;ch[p][c] = np;}lstp = ch[p][c];
}signed main()
{scanf("%s", s);init();int last = 0;for (int i = 0; s[i]; ++i) {if (i)	s[i] = (s[i] - 'a' + last) % 26 + 'a';	insert(s[i] - 'a', i);last = cnt[lstp];printf("%d ", last);}puts("");return 0;
}