回文树与回文后缀链接

一次追加为什么最多只多一种回文 ​

设旧文本为 $T$，新文本为 $Tc$。任何新内容都必须有一次出现碰到新加的末字符，否则它早已在 $T$ 中。因此新内容只能是新前缀的回文后缀。

令 $P$ 为最长回文后缀，$Q$ 是一个更短的回文后缀。由于 $P$ 回文且 $Q$ 本身回文，$Q$ 同时是 $P$ 的前缀。这个前缀出现严格早于 $P$ 的末端，已经完全位于旧文本 $T$。所以 $Q$ 不是新内容，唯一可能新建的是 $P$。[1]

从空文本连续追加 $n$ 次，普通节点至多 $n$ 个。每个非单字符回文去掉首尾后，内部回文与外字符唯一确定它的入扩展边；单字符则唯一来自虚根。因此扩展边也至多 $n$ 条，而不是“节点线性，所以边当然线性”。

沿后缀链接寻找能被新字符包住的内层 ​

新最长回文若不止一个字符，必形如 $cQc$，其中 $Q$ 是旧前缀的回文后缀。由长到短沿旧 last 的后缀链接检查：在 $Q$ 前面紧邻的字符是否也是 $c$？第一个能通过者形成最长答案。若一直失败，虚根的长度 $-1$ 让比较位置恰好落在刚加入的字符本身，必然通过，输出单字符。

如果扩展边 next[Q][c] 已存在，直接复用那个节点。否则创建 $P=cQc$。为了确定新节点的后缀链接，从 link[Q] 继续同样的查找；找到次长的可扩张内层，再沿其 $c$ 边，就得到 $P$ 的最长真回文后缀。该目标早已存在，因为上一段证明它在旧文本中已经出现。

完整的追加实现 ​

class Eertree:
    def __init__(self):
        self.text = []
        self.length = [-1, 0]
        self.link = [0, 0]
        self.next = [{}, {}]
        self.first_end = [-1, -1]
        self.as_longest = [0, 0]
        self.last = 1

    def _extendable(self, v, i):
        while i - self.length[v] - 1 < 0 or self.text[i - self.length[v] - 1] != self.text[i]:
            v = self.link[v]
        return v

    def add(self, c):
        if not isinstance(c, str) or len(c) != 1:
            raise ValueError('add expects one Unicode code point')
        self.text.append(c)
        i = len(self.text) - 1
        q = self._extendable(self.last, i)
        created = c not in self.next[q]
        if created:
            v = len(self.length)
            self.length.append(self.length[q] + 2)
            self.link.append(1)
            self.next.append({})
            self.first_end.append(i)
            self.as_longest.append(0)
            self.next[q][c] = v
            if self.length[v] > 1:
                p = self._extendable(self.link[q], i)
                self.link[v] = self.next[p][c]
        self.last = self.next[q][c]
        self.as_longest[self.last] += 1
        return created

    def occurrences(self):
        counts = self.as_longest.copy()
        for v in range(len(counts) - 1, 1, -1):
            counts[self.link[v]] += counts[v]
        return counts

这里用字典映射理路字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。保存稀疏扩展边。Python dict 的通常期望查找成本为常数，不能据此声称任意哈希碰撞输入下也有最坏常数界。若换成有序平衡树字典，则字符查询带 $O(\log (\sigma +1))$ 因子，$\sigma$ 为已用字符数。

从最长后缀恢复一个可检查的节点表 ​

依次读入 abacdcabba，每步的最长回文后缀为：

这一实例每次恰好新建一个普通节点，最终十个节点。长度八时 last 是 bacdcab，追加第二个 b 时，长七后缀前的字符 a 不能与新 b 配对；回退到 b，它前面的字符仍是 a，再次失败；回退到空根时，前一字符正是 b，于是得到新回文 bb。

下一次追加 a，旧后缀 bb 前面的 a 通过，形成 abba。新节点的后缀链接不是 bb：bb 并非 abba 的后缀。真正最长真回文后缀是 a。图中特别分开扩展边 bb→abba 与后缀链接 abba→a，可用这个例子检查实现是否混淆两种父关系。

并非每次追加都会创建节点。对 abca，最后一个 a 的最长回文后缀就是已存在的单字符 a，返回 False，仍只有三种不同回文。空串则没有普通节点，出现次数列表虽保留根槽，但两个根槽都不属于非空回文统计结果。

在线总成本不是每次追加的最坏成本 ​

先读入 $a^m$，再追加 b，就会从长度 $m$ 逐一退到虚根，单次追加可花 $\mathrm{\Theta }(m)$ 时间。基本版本只保证整段只追加过程的摊还界。若反复“加 b、删除 b”，同样的长链可能被重新走许多遍；本页没有提供删除操作，不能把只追加的证明直接搬到支持回滚的接口。[1, §3.2]

把两次查找都纳入摊还证明 ​

第一轮查找可用摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。直接记账。令 ${\ell }_t$ 为长 $t$ 前缀的最长回文后缀长度，${\ell }_0=0$。每沿一次后缀链接，候选长度至少减少一；最后一次扩展增加二。因此第 $t$ 次追加的失败回退数不超过 ${\ell }_{t-1}+2-{\ell }_t$，全程相加至多 $2n$。

第二轮查找不能在证明中漏掉。令 $h_t$ 为第二长的回文后缀长度，允许空回文；没有非空真回文后缀时为零。若第一轮选中的内层是 $Q$，第二轮从 link[Q] 开始，其长度至多 $h_{t-1}$。查找成功后扩展二，得到长度 $h_t$，所以这轮失败回退数至多 $h_{t-1}+2-h_t$。

未新建节点时不执行第二轮，但仍有 $h_t\le h_{t-1}+2$：删去新第二长后缀的首尾，所得内层是旧前缀的真回文后缀；若它反而是旧最长后缀，那么扩展出的就会是新最长后缀，与“第二长”矛盾。长度零或一的情况直接满足不等式。因此可以对所有追加相加，把第二轮总回退也界为 $2n$，而不是只在创建节点的零散时刻错误地望远镜求和。

每次追加只做常数次字典操作，故平衡树版本总时间 $O(n\log (\sigma +1))$、空间 $O(n)$；常数字母表或合适哈希假设下总时间为 $O(n)$。若每个节点都开 $\sigma$ 个稠密槽，空间应记为 $O(n\sigma )$，只有 $\sigma$ 是固定常数时才简写成线性。

出现次数沿链接汇总 ​

追加后只给当前 last 的 as_longest 加一，记录“多少个前缀以这个节点作为最长回文后缀”。这还不是所有出现次数。对每个前缀，其全部较短回文后缀恰在 last 的链接链上，所以把最长后缀的贡献向链接父亲传播即可。

创建节点时，后缀链接的目标必已存在，目标编号小于新节点。于是按创建编号倒序，令 counts[link[v]]+=counts[v]，就保证每份子贡献在继续上传前已经汇总完成。代码先复制原始计数，使重复调用 occurrences 不会重复累加；构建仍可继续，下一次查询重新从 as_longest 开始汇总。返回列表中的根槽仅为中间累计，不作为空回文出现数解释。

对主例，a,b,c,d 的计数依次为 $4,3,2,1$，其余六种回文各出现一次，总和十六，与半径数组独立得到的结果一致。a^4 则应报告 a:4,aa:3,aaa:2,aaaa:1。能够从节点创建表、链接关系、原始计数独立复算这个字典，比只报告“有四个节点”多完成了真正的索引接口。

最少回文分解理路最少回文分解动态规划Minimum palindromic factorization · Palindromic length · 最小回文切分以已覆盖的前缀长度为状态，枚举全部非空回文末块，计算最少块数并重建切点，区分线性回文预处理与二次方转移成本。可以在每次追加后沿 last 的链接枚举所有合法末块。树的构建成本虽然线性，这个额外枚举仍可能访问二次方个回文出现；数据结构小，不意味着所有基于它的算法都会自动变快。