编程面试：如何用回文树（Eertree）在线统计不同回文子串？

题干与适用场景

给定字符流 s[0..n)，每次只追加一个字符。追加后需要维护不同回文子串的数量、每个回文的出现次数，并返回当前前缀的最长回文后缀。要求在线处理，不能每次重新枚举所有子串。

回文树（Eertree）为每个不同回文建立一个节点，边表示两侧追加同一字符，suffix link 指向最长的真回文后缀。强回答要说明两个特殊根节点、如何寻找可扩展的回文后缀，以及为什么最多新增一个节点。

面试官考察点

• 是否能正确区分长度 -1 与长度 0 的两个根。
• 是否理解 last、最长回文后缀和 suffix link 的含义。
• 是否能在追加字符时找到可扩展节点并建立转移。
• 是否知道节点数、构建时间和空间上界均为 O(n)。
• 是否处理重复字符、空串、字符集表示和计数传播顺序。
• 是否能把结构扩展到回文分割或滑动窗口等变体。

回答前需要澄清的问题

1. 输入是一次性字符串还是只能右端追加的流？是否需要删除左端字符？
2. 出现次数按结束位置计数，还是要统计最终的总出现次数？
3. 字符集是小写字母、Unicode，还是需要支持任意整数 token？
4. 需要返回最长回文本身、节点编号，还是只返回长度和计数？
5. 是否要在线回答每个前缀的回文分割，或者只维护 distinct palindrome 集合？

30 秒回答框架

我维护两个根：长度 -1 的奇根和长度 0 的偶根；每个普通节点保存回文长度、到最长真回文后缀的 suffix link，以及按字符索引的转移。last 表示当前前缀的最长回文后缀。追加字符 c 时，沿 suffix link 跳转，直到找到两侧都能放入 c 的节点；若没有 c 转移就新建节点，suffix link 由新回文的最长真回文后缀确定。每次最多新建一个节点，因此构建是 O(n)，节点计数沿 suffix link 逆序传播后得到总出现次数。

分步骤深入解答

1. 两个根和节点字段

奇根长度为 -1，它可以把任意字符视为两侧匹配的哨兵；偶根长度为 0，表示空回文。普通节点保存 len、link、next、occ 和一个代表性结束位置。last 初始指向偶根，表示空前缀没有非空回文后缀。

2. 找到可扩展的后缀

追加字符 c 到位置 pos 后，从 last 开始检查节点对应回文左侧的字符是否等于 c。若不等，就令 v = link[v] 继续跳。因为 suffix link 串联的是回文后缀，第一次满足条件的节点就是当前前缀可扩展的最长回文后缀。

while s[pos - 1 - len[v]] != c:
    v = link[v]

访问奇根时需要哨兵边界，工程实现通常在字符串前面放一个不属于字符集的哨兵，避免负索引。

3. 建立转移和新节点

若 next[v][c] 已存在，它就是追加后的新 last，只需把该节点的 occ 加一。否则创建长度 len[v] + 2 的节点，并设置 next[v][c]。长度为 1 的节点 suffix link 直接指向偶根；更长节点则从 link[v] 开始继续寻找可扩展后缀，并取其 next[c]。

4. 为什么最多新增一个节点

追加一个字符后，所有新产生的回文都必须以这个字符结尾。它们中只有最长者不是旧前缀的子串，其余新回文都是该最长回文的 suffix link 链上的已有节点。因此每个位置最多创建一个不同回文节点，节点总数不超过 n + 2。

5. 出现次数传播

在线阶段可把每个位置的最长回文后缀节点 occ 加一。输入结束后，按节点长度从大到小处理，把 occ[v] 加到 occ[link[v]]，这样每个回文的 occ 就包含所有以它为后缀的更长回文出现次数。若只要 distinct 数量，直接返回普通节点数即可。

6. 回文分割扩展

若要计算前缀的最少回文切分，可在每个位置沿 last 的 suffix link 链枚举以该位置结尾的回文，再做 dp[pos] = min(dp[pos - len[v]] + 1)。朴素沿链可能退化为 O(n^2)；可以维护 series link，把长度差相同的链段合并，得到线性或近线性的优化，必须先说明约束再选择实现。

7. 边界、字符集与复杂度

空串只有两个根；重复字符会反复命中已有转移，不能重复建点。小字符集可用定长数组，空间是 O(n * alphabet)；大字符集应使用哈希表或有序映射，复杂度要写成 O(n) 期望或 O(n log σ)。在只追加模型下，总体构建时间为 O(n)（哈希转移按期望计），空间为 O(n) 加转移存储。

高质量示范回答

我会先明确输入是右端追加、字符集和出现次数定义。结构有长度 -1 与 0 两个根，普通节点代表一个不同回文，last 是当前前缀的最长回文后缀。追加 c 时沿 suffix link 找到能在两侧包住 c 的最长节点；若转移不存在就创建 len + 2 的新节点。新节点长度为 1 时 link 指向偶根，否则从父节点 link 链寻找对应转移。每个位置最多创建一个节点，所以构建 O(n)；记录每次 last 后按长度降序向 link 汇总，即可得到每个回文的总出现次数。删除、任意位置插入和大字符集会改变实现与复杂度，我会在约束确认后再选数据结构。

常见错误

• 只有一个空根 → 奇偶长度边界无法统一 → 保留 -1 和 0 两个根。
• 直接从根重新找后缀 → 失去在线线性性质 → 从 last 沿 suffix link 跳转。
• 把 last 当最长回文子串 → 它只保证是当前前缀的最长回文后缀。
• 新建节点后 link 指向父节点 → link 应指向最长真回文后缀的节点。
• 每次都把所有回文 occ 加一 → 会重复计数 → 先记录结束位置，再逆序沿 link 传播。
• 用固定小数组处理任意 Unicode → 可能溢出或错误合并 → 明确字符编码和映射策略。

追问及应对

和 Manacher 算法如何选择？

Manacher 适合一次性求每个中心的最长回文半径；Eertree 直接表示所有不同回文，天然支持在线追加、节点级计数和后缀链查询。若需求只有静态最长回文，Manacher 通常更简单。

如何返回当前最长回文的内容？

节点保存任意一次结束位置 endPos，配合 len 从原串切片即可。在线流若不保留全部输入，需要额外的环形缓存或外部存储。

如果要统计每个回文的出现次数，为什么要逆序传播？

更长回文的每次出现也意味着其 suffix link 回文出现一次。按长度从大到小传播可保证子节点贡献已经汇总，再累加到父节点，不会遗漏嵌套出现。

能否支持左端删除？

普通 Eertree 只支持右端追加。滑动窗口需要双端回文树或重建/分块方案，选择取决于窗口大小、删除比例和延迟目标。

next 用哈希表会改变什么？

哈希表使每次转移查找为期望 O(1)，总体期望 O(n)；最坏情况取决于哈希实现。若需要确定性边界，可使用有序映射并接受 O(log σ) 因子。