基本元素
节点：原串的一个本质不同的回文子串。
长度 len[o]：回文子串长度。
转移边 ch[o][x]：两边同时加字符 \(x\)。
失配边
fa[o]：最长回文后缀。到根的路径是所有回文后缀。
有两个根，奇根1 和
偶根0，fa[0] = 1, len[1] = -1。
常用的构造方法是均摊 \(O(n)\) 的，证明很简单，略。
代码：
char s[N], *now = s;
std::array<int, 26> ch[N];
int fa[N], len[N], cnt, dep[N];
int jmp(int x) {
for (; now[~len[x]] != *now; x = fa[x]) ;
return x;
}
int ins(int x) {
static int p, q;
now++;
if (!ch[p = jmp(p)][x]) {
len[q = ++cnt] = len[p] + 2;
fa[q] = ch[jmp(fa[p])][x];
ch[p][x] = q;
dep[q] = dep[fa[q]] + 1;
}
return p = ch[p][x];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> s + 1;
int n = strlen(s + 1), k = 0;
fa[0] = 1;
len[1] = -1;
cnt = 1;
for (int i = 1; i <= n; i++) {
s[i] = (s[i] - 'a' + k) % 26 + 'a';
k = dep[ins(s[i] - 'a')];
std::cout << k << " ";
}
return 0;
}性质
本质不同回文子串数：除根以外的点数。
回文子串出现次数：失配树上对应节点子树大小
siz[o]。奇偶性：回文树边两端点
len奇偶性相同，但失配树边不是。不超过一半的最长回文后缀对应节点
f[o]：
if (len[q] <= 2) {
f[q] = fa[q];
} else {
for (int &i = f[q] = f[p]; now[~len[i]] != *now || (len[i] + 2 << 1) > len[q]; i = fa[i]) ;
f[q] = ch[f[q]][x];
}回文串的回文后(前)缀与其 \(\rm Border\) 一一对应。某个串的回文后(前)缀长度可以拆分为 \(O(\log n)\) 个等差数列。
设 \(v\) 为回文串 \(u\) 的最长回文严格前(后)缀，若 \(2|v|\geq |u|\)，那么 \(v\) 只会在 \(u\) 中恰好匹配两次，分别作为前缀和后缀。
根据性质5，用 slink[o]
来表示上一个等差数列的开头，一直跳 slink 最多会跳
log 次，可以将插入复杂度变为单次最坏 \(O(\log n)\)，在回溯操作时保证了复杂度最坏
\(O(n \log n)\)（ICPC2020昆明F）。
int jmp(int x) {
for (; now[~len[x]] != *now; x = now[~len[fa[x]]] == *now ? fa[x] : slink[x]) ;
return x;
}
diff[q] = len[q] - len[fa[q]];
slink[q] = diff[q] == diff[fa[q]] ? slink[fa[q]] : fa[q];性质 5, 6 结合 \(\rm Border\) 的性质十分有用，回文树的大部分解题思路也都是基于这些性质的。
其他技巧
有一个非均摊复杂度的插入方法是记录
fch[o][x]表示要插入x应该跳到哪个祖先，每次要复制fch[o]数组，所以复杂度是 \(O(n \Sigma)\)。回文树支持双端插入，只要记录前后端的
p即可。整个串变成回文串时，要同时更新前后端的p。相等问题转化为回文问题：
最后修改于 2021-11-04