回文自动机原理与实现

回文自动机原理与实现

概述

回文自动机(简称PAM,又称回文树,Palindromic Tree)是一种用于处理回文串的结构,在其结构内可以找到原串中的所有回文子串,经由APIO2014推广。下面对其原理及实现进行介绍。
本文中所有图片来自网络,感谢其作者的贡献。

结构

palind tree struct - 回文自动机原理与实现
如图为串abba的PAM示意图,其中,实现表示回文串的扩展转移边,虚线表示后缀链接。

回文树

回文树是PAM的一部分,一个PAM包含两棵回文树,分别代表奇偶回文串。每棵回文树上,所有节点(除树根以外)都代表了一个回文子串。每条转移边上都有一个字符,若某点对应的回文子串为$S$,它的一条出边上字符为$c$,则会转移至一个代表$c+S+c$串的节点。从树根出发的每条路径,都对应着一个回文子串,如果将路径上边的字符顺次连接,将会得到回文串的右半部分。

节点信息

  • 每个节点上记录对应回文串的长度$\mathrm{len}(u)$,若节点$v$是节点$u$转移而来的,则有$\mathrm{len}(v) = \mathrm{len}(v) + 2$。为了方便,我们规定,偶回文树树根$\mathrm{len}(rt_0)=0$,奇回文树树根$\mathrm{len}(rt_1)=-1$。
    abba的PAM中,节点$u$代表串bb,节点$v$代表串abba,存在$u \rightarrow v$的转移边,$\mathrm{len}(u)=2$且$\mathrm{len}(v)=4$。
  • 每个节点记录该节点对应回文串的出现次数$\mathrm{siz}(u)$。在回文树中,除了根节点以外,所有节点满足$\mathrm{siz}(u)>0$。

转移边

转移边$u \rightarrow v$对节点的意义是,将$u$对应的回文串左右两边加上同一个字符$c$得到节点$v$对应的回文串。由于$u$对应的回文串是$v$对应的回文串的子串,因此,$v$对应的回文串出现的地方,$u$对应的回文串也出现了。

后缀链接

  • $u$的后缀链接指向$v$,记作$\mathrm{fail}(u)=v$,当且仅当$v$对应的回文串是$u$对应的回文串的一个后缀,且不存在其他的$v’$,使得$\mathrm{len}(v’) > \mathrm{len}(v)$且满足上一句话的性质。这里的后缀链接的意义与AC自动机、KMP匹配算法的fail数组意义很像。
    例如,对于abba的PAM,对应abba的节点$u$与对应a的节点$v$,存在$\mathrm{fail}(u)=v$。
  • 为了方便,我们规定,偶回文树树根的后缀链接指向奇回文树树根,即$\mathrm{fail}(rt_0)=rt_1$。
  • 后缀链接构成了一棵以奇回文树树根为根的有根树,方向从叶子指向根。

构造

流程

PAM的构造法在字符集为常数且较小时,是线性复杂度的。与SAM相似的是,PAM的构造法也是一个增量算法,因此,应该解释为,每次在母串后插入一个字符,更新PAM的复杂度是$O(1)$的。
PAM中,我们需要记下上一次插入的节点位置,即$lst$。
下面,我们结合例子解释插入的过程。

如图,为串abba的PAM,我们向其插入新字符a
pam cons1 - 回文自动机原理与实现

  1. 从上一次插入的节点位置$lst$开始沿$\mathrm{fail}(u)$上跳,找到第一个节点,使得该节点对应的一个母串的后缀后加上插入的字符$c$构造出了一个新的回文后缀。
    在本例中,abba后加入字符a构成的新串是abbaa,这一过程实际上是找到一个新串的一个最长回文后缀,也就是aa的父节点,我们找到的是偶回文树的树根$0$。
  2. 若查询到该回文串已存在节点,则对该节点$\mathrm{siz}(u)$加1。
  3. 若不存在该回文串的节点,则在父节点下新建节点,并采用与1相似的过程,从父节点沿$\mathrm{fail}(u)$上跳,直到找到一个第一个最长的回文后缀,从而计算出该节点的$\mathrm{fail}(u)$值。
    在本例中,aa回文串的最长回文后缀是a,容易发现,从父节点$0$开始上跳,会跳到奇回文树根$1$,从而找到对应的最长回文后缀节点$2$,即对于新加点$u=6$,有$\mathrm{fail}(6)=2$。
  4. 更新PAM的$lst$值及刚才插入的回文后缀的$\mathrm{siz}(u)$值。

经过上面一通处理,现在,PAM的结构变为了下图的样子。
pam cons2 - 回文自动机原理与实现

实现

参见例题。

例题:[APIO2014]回文串

点击标题进入文章。

常见应用

本质不同回文子串数目

即后缀树中节点的数量。

每个回文子串出现的次数

先按逆序(拓扑序)更新父节点$\mathrm{siz}(u)$值然后就可以直接拿来用了。

参考资料



1 thought on “回文自动机原理与实现”

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据