这篇文章将提出 回文树 的概念,一种解决回文串相关问题的优美数据结构。

感谢它的发明者 Mikhail Rubinchik,在 Petrozavodsk Summer Camp 2014 中向我们讲述了这一概念,使得这篇文章的创作成为可能。

结构

和其他所有树形结构一样,回文树由节点构成。在这里,每个节点代表了一个回文串。

四个节点的回文树
四节点回文树的样例

在节点之间有边相连。一条从 $u$ 连至 $v$ 的树边上会标有一个字母 $x$,表示在 $u$ 处的回文串左右加上一个 $x$ 得到 $v$ 处的回文串。

‘aba’ 由 ‘b’ 在左右两边各添加一个 ‘a’ 得来

同时也存在着一些非树边,我们称之为 $fail$ 指针。从 $u$ 指向 $v$ 的 $fail$ 指针表示 $v$ 是 $u$ 的最长回文后缀。当然,$u \neq v$。

‘a’ 是 ‘aba’ 的最长回文后缀

在实际使用中,我们不记录每个节点具体表示了什么串,我们记录的是它的长度,$fail$ 指针,以及子节点的编号。

构建

初始化

作为一棵树,回文树有个不寻常之处:它有两个根节点。根节点 $0$ 用来处理长度为偶数的回文串,而根节点 $1$ 用来处理长度为奇数的。

特别地,$fail(0)=1$,而 $len(1)=-1$,因为子节点的长度一定是父节点 $+2$。

插入和匹配

当我们插入一个新的字符 $x$ 时,最终形成的回文串一定是在已有的回文串的左右各加上 $x$。我们设这个新回文串为 $N$,它包含的最长回文子串为 $C$,我们要寻找的是下面式子中的 $xC$。

$$N = x C x$$

也就是,我们从上个字符代表的回文串开始,判断这个回文串的左边一个字符是否等于 $x$,如果不是则跳到 $fail$ 指针指向的后缀字符串,不断进行,直到找到满足的回文串 $C$。这个回文串 $C$ 左右加上 $x$ 之后,就是以现在的 $x$ 结尾的最长回文串 $N$。

找到最长回文串之后,还需要构建它的 $fail$ 指针,也就是 $x$ 结尾的次长 回文串。$N$ 由 $C $ 转移而来,$N$ 的 $fail$ 也由 $C$ 的 $fail$ 转移而来。用下面这个式子表示,$xC’$ 就是 $C$ 的 $fail$ 的一个后缀,$C’$ 是一个回文串。

$fail(N)=xC’x$

应用

我们发现,一个字符串的回文树的构建,帮助我们找到了它所有本质不同的回文子串的长度和出现次数。我们可以用这个性质解决很多问题。

例:[APIO2014]回文串

给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 $s$,求所有回文子串中的最大存在值。

思路

实际上就是个裸题啦。但有一点要注意,计算次数的时候需要从深度大的点开始向上沿着 $fail$ 累加,因为一个回文串出现也代表着它指向的 $fail$ 的出现。

代码

  1. kal0rona
    Jan 08, 2019

    神仙

    Reply