再学串串（六）：回文自动机动自文回：）六（串串学再
clx201022
·
·
算法·理论
被打回 @ 2026-05-15 19:40
拒绝原因
数学公式外应使用中文全角标点；【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格。
已严肃修改。
以防你不知道，本文的标题灵感来自于木又寸寸又木。
至于括号为什么也翻转……灵感可能来源于哥群周刊罢。
过去的章节节章的去过
- 再学串串（一）：我真的学会 KMP 了吗？评「clx201022 式的傲慢」
- 再学串串（二）：AC 自动机不是自动 AC 机
- 再学串串（三）：被构造自动机上计数 DP 题吓晕
- 再学串串（四）：后缀是后缀的后缀是后缀的后缀
- 再学串串（五）：谁会不喜欢可爱的小马（拉车）呢？
目前已同步在博客园更新。
第六站：回文树文回：站六第
众所周知，「AC 自动机」往往不能让人 AC；「后缀自动机」实际上是「前缀性」的；「中原第一雄关徐州城」不是第一雄关，不在中原，甚至都不是城；「上海爱丽丝幻乐团」不在上海[^shanghai]，没有爱丽丝，更不是幻乐团。
「回文自动机」也不是一个用来判断一个串是否回文的自动机，相反，其更像是一个用来高效存储一个串 T 中所有回文串的树形数据结构。所以，在此也将其称为「回文树」。[^eertree]
回文存储储存文回
相信大家都在小学二年级的科技史课上学过：
回文树（EER Tree，Palindromic Tree，也被称为回文自动机）是一种可以存储一个串中所有回文子串的高效数据结构．最初由 Mikhail Rubinchik 和 Arseny M. Shur 在 2015 年发表．它的灵感来源于后缀树等字符串后缀数据结构，使用回文树可以简单高效地解决一系列涉及回文串的问题．
（此处为 OI Wiki 原文，不做改动）
假设这两位就是你和你的好朋友，现在你们要发明回文树，那么你们应该怎么做呢？
首先，存储回文串事实上只需要存储半边（另一半翻转过去再拼上即可）。如 \texttt{EERTREE} 真正需要存下来的部分就只有 \texttt{TREE} 这一部分，另一部分翻转拼接即可。
能独立默写马拉车[^Manacher]算法并且深谙回文性质的你明白，一个长度不小于 2 的回文串总是可以由一个更短的回文串通过在首尾两段各加入一个字符取得[^huiwen]，而不断在两边添加字符这一点和自动机是同构的。
由此回文自动机的每个节点都与一个存在于 T 中的回文串一一对应。但区别于一般的自动机，回文自动机每条转移边代表的是在首尾两边各增加一个字符；并且回文自动机接受的也不是「T 中的所有回文串」，而是「T 中的所有回文串的后一半」。
（以 T=\texttt{EERTREE} 为例）
:::info[为什么不直接匹配 T 中的所有回文串？]
如果想要构造一个接受「T 中的所有回文串」的自动机，就需要对回文树中每个状态额外构造一条回退的路径，如对于串 \texttt{EERTREE} 经过 T->R->E->E 后还需要再经过 E->E->R->T 回来。（需要构造额外状态并且还需要注意处理不同状态间的转移冲突问题，如 T->R->E->E->R->T 同时也是一条可行的路径，所以还需要合并一些状态，总之就是特别复杂，既麻烦也没有必要）
:::
此外，回文串分奇数长度和偶数长度，聪明的你选择将两种回文串分开存储。在状态上体现为回文树分别有两个根，分别为「奇根」和「偶根」（其实怎么称呼都可以，不过此处暂且如此称呼）。「奇根」下的第一条转移边代表只添加一个字符，其他转移边都是首尾同时添加同一个字符。
你的朋友还想同时维护每个串的长度，每个转移边代表着 2 个字符的长度差——然而这样算会导致「奇根」的长度为 -1。但仔细一想，「奇根」的长度为 -1 又有什么问题呢？同时往首尾两边各增加一个相同字符，最后却只剩一个字符，那原来的长度不就是 -1 吗？
:::info[一种不太严谨的解释]
（不同于「空字符串」没有任何字符，「奇根」对应一个「坑」字符——这个「坑」字符抵消了其他字符，最后才会出现「往首尾两边各增加一个相同字符，最后却只剩一个字符」的情况）
:::
回文树应该还能从前往后扫一遍 T 就能以 \Theta(n=|T|) 的时间复杂度构造。考虑抄袭借鉴 KMP 自动机中的 fail 指针，对每个回文串存储其的最长回文真后缀——同构于 Border 理论与 Linktree，这也等同于存下了每个回文串的所有回文后缀。
注意边界情况：「偶根」的 fail 指针是连到「奇根」上的。
算法实现现实法算
有了这些从前往后加每个就可以一点点构造出回文树了\~
假设对于 T 已构造出它的回文树，现在要求 T'=T+c 的回文树。
仅需考虑所有 T' 的回文后缀为增量。假设新增了一个 T' 的回文后缀 S'，T 中必然存在一个回文后缀 S 满足 c+S+c = S'。此时 S 在 T 的回文自动机中必有一个唯一对应的状态 s。（特别地，可能有 S'=c，可以理解为 S 的长度为 -1，对应「奇根」）
所有可能的 $S$ 都求出来了，需要全部维护吗？只需要维护可能的最长 $S$ 即可。
设最长的 $S$ 为 $S_1$，任意一个其他的可能 $S$ 为 $S_2$。因为 $S_2$ 必然为 $S_1$ 的一个真后缀，所以 $S_2'$ 必然也为 $S_1'$ 的一个真后缀。根据回文串的性质，$S_2'$ 必然也为 $S_1'$ 的一个真前缀，即 $S_2'$ 为 $T$ 的一个子串，此时 $s_2'$ 必然已经存在，至多需要新建一个状态 $s_1'$（有时甚至连 $s_1'$ 都已经存在）。这也正好证明了该构造算法是 $O(|T|)$ 的。
### 例题例
:::success[[P3649 \[APIO2014\] 回文串](https://www.luogu.com.cn/problem/P3649)]
新建节点的顺序即为拓补序。树上前缀和统计再取最大值即可。
注意新建节点时如果当前状态 $s$ 对应字符串 $S$ 不存在非空回文后缀，$fail$ 指针要连到偶根上。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<int maxsz>
class PAM
{
int sz, tot, lst;
struct state
{
int cnt, len, fail;
unordered_map<char, int> ch;
state(int len_ = 0) : cnt(0), fail(1), len(len_), ch() {}
} st[maxsz];
char s[maxsz];
int getNode(int len_)
{
st[sz] = state(len_);
return sz++;
}
int getFail(int x)
{
while(s[tot - st[x].len - 1] != s[tot]) x = st[x].fail;
// len = -1 时必等
return x;
}
public:
void clear()
{
sz = 0;
s[tot = 0] = '#'; // 不可能字符
getNode(-1); // 奇根
getNode(0); // 偶根
st[1].fail = 0;
lst = 1; // 偶根
}
PAM() {clear();}
void insert(char c)
{
s[++tot] = c;
int now = getFail(lst); // 此时 now 必然满足可扩展
if(!st[now].ch.count(c))
{
int x = getNode(st[now].len + 2); // 往后新建一个节点
int ff = getFail(st[now].fail);
if(!st[ff].ch.count(c)) st[x].fail = 1;
else st[x].fail = st[ff].ch[c]; // 找到下一个满足可扩展的
// 否则默认没救
st[now].ch[c] = x;
}
++st[lst = st[now].ch[c]].cnt;
}
ll solve()
{
ll ans = 0;
for(int i = sz - 1; i >= 0; i--) st[st[i].fail].cnt += st[i].cnt;
for(int i = 0; i < sz; i++) ans = max(ans, st[i].len * (ll)st[i].cnt);
return ans;
}
};
PAM<300001> pam;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
string s;
cin >> s;
for(auto c : s) pam.insert(c);
cout << pam.solve();
return 0;
}
```
:::
:::success[[P4555 \[国家集训队\] 最长双回文串](https://www.luogu.com.cn/problem/P4555)]
EERTREE 可以方便求出每个位置为右端点的回文串，那么倒过来就容易求每个位置为左端点的回文串。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int maxn = 1e5;
template<int maxsz>
class PAM
{
int sz, tot, lst;
struct state
{
int cnt, len, fail;
unordered_map<char, int> ch;
state(int len_ = 0) : cnt(0), fail(1), len(len_), ch() {}
} st[maxsz];
char s[maxsz];
int getNode(int len_)
{
st[sz] = state(len_);
return sz++;
}
int getFail(int x)
{
while(s[tot - st[x].len - 1] != s[tot]) x = st[x].fail;
// len = -1 时必等
return x;
}
public:
void clear()
{
sz = 0;
s[tot = 0] = '#'; // 不可能字符
getNode(-1); // 奇根
getNode(0); // 偶根
st[1].fail = 0;
lst = 1; // 偶根
}
PAM() {clear();}
int insert(char c)
{
s[++tot] = c;
int now = getFail(lst); // 此时 now 必然满足可扩展
if(!st[now].ch.count(c))
{
int x = getNode(st[now].len + 2); // 往后新建一个节点
int ff = getFail(st[now].fail);
if(!st[ff].ch.count(c)) st[x].fail = 1;
else st[x].fail = st[ff].ch[c]; // 找到下一个满足可扩展的
// 否则默认没救
st[now].ch[c] = x;
}
++st[lst = st[now].ch[c]].cnt;
return st[lst].len;
}
};
PAM<maxn + 1> pam1, pam2;
int L[maxn + 1], R[maxn + 1];
int ans;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
string s;
cin >> s;
for(int i = 0; i < s.size(); i++) L[i] = pam1.insert(s[i]);
for(int i = s.size() - 1; i >= 0; i--) R[i] = pam2.insert(s[i]);
for(int i = 1; i < s.size(); i++) ans = max(ans, L[i - 1] + R[i]);
cout << ans;
return 0;
}
```
:::
## 友链链友
- 《[回文自动机小记](https://www.luogu.com.cn/article/nffjwrmx)》@[command\_block](luogu://user/58705)
- [EERTREE: An Efficient Data Structure for Processing Palindromes in Strings, Mikhail Rubinchik and Arseny M. Shur](https://arxiv.org/pdf/1506.04862)
- 《[原创 - 1](https://www.luogu.com.cn/article/jyivt87v)》UniGravity
- [Another Graph Editor](https://anacc22.github.io/another_graph_editor/)
## 创作声明声作创
本文遵循 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans) 协议。
保证本文未使用任何 AI 工具辅助创作。
转载例如下：
> ```py
> [原文](https://www.luogu.com.cn/article/one17zp5)作者为 [clx201022](https://www.luogu.com.cn/user/552688)，转载人保证会遵循 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans) 协议：以适当的方式署名，不以盈利为目的进行转载，并以相同方式共享此文。
> ```
[^Manacher]: Manacher，「马拉车」为音译。
[^huiwen]: 我们认为空字符串也是一个回文串。
[^shanghai]: （一个过时的回文笑话）上海自来水来自海上。
[^eertree]: 你说的对，但一棵「回文树」往往包含两棵树——自动机上转移边构成的外向树和 $fail$ 指针构成的内向树。