隐藏
回文自动机学习笔记 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

回文自动机学习笔记

三大自动机排名最后的自动机:回文自动机。
为什么排名最后?因为实在没什么太多的用处。
回文自动机又称为回文树,它们是一个含义。

定义

一个回文自动机中包含两个结构:内部回文树(简称为回文树)和$fail$树。
每一个结点同时存在于这两个结构中。
若将$s$建立回文自动机,则称$s$是该回文自动机的母串。
记$\left|S\right|$是字符串$S$的长度。
记$[c_1,c_2,\ldots,c_n]$为字符$c_i$组成的长度为$n$的字符串。

回文子串

若$t$是$s$的子串且$t$是回文的,则称$t$是$s$的回文子串。

回文后缀

若$t$是$s$的后缀($s\neq t$)且$t$是回文的,则称$t$是$s$的回文后缀。

最长回文后缀

$s$的最长回文后缀$t$是$s$的所有回文后缀中最长的一个。
注意一个串可以不存在最长回文后缀,定义它的回文后缀只包含一个空串。

回文树

一个串的回文树由两棵树组成,他们的根分别为$even,odd$。
树上的每一个结点表示一个字符串,与母串的回文子串一一对应。
树上的每一条边上有一个字符$c$,代表该点表示的回文子串$s$经过该边后到达表示回文子串$c+s+c$的结点。

定义根$even$表示的字符串是空串,根$odd$表示的字符串是一个长度为$-1$实际不存在的字符串。
根$odd$的儿子是长度为$1$的回文子串,根$even$的儿子是长度为$2$的回文子串。

在本文的叙述中,我们用树上的结点指代其代表的字符串。

后缀链接与fail树与fail链

结点$u$的后缀链接指向$v$当且仅当$v$是$u$的最长回文后缀。
特别的,定义$next(odd)=next(even)=odd$。
注意,这里定义的根的后缀链接没有含义,仅仅是为了编程方便。

由后缀链接组成的树形结构称为$fail$树。
结点$u$在$fail$树上到根的路径称为$fail$链。

回文自动机

对于回文自动机上的每个结点,我们维护三个信息:

  • $len$,表示该点对应的回文子串的长度。
  • $child[c]$,该点经过$c$的转移边到达的状态。
  • $next$,后缀链接。

空间复杂度线性证明

对于后缀自动机,由于状态太多,因此每个结点表示多个字符串。而回文自动机的一个结点仅表示了一个字符串,那么它的空间复杂度怎么样呢?

定理1

对于一个字符串$s$,不同的回文子串的个数最多只有$\left|s\right|$个。

我们使用数学归纳法证明上述定理:
证明思路:产生的子串很多以前都出现过。

  • 当$\left|s\right|=1$时,只有一个回文子串,结论成立。
  • 当$\left|s\right|\gt1$时,设$s=s’c$,其中$c$是$s$的最后一个字符,并且结论对$s’$成立。考虑以$c$结尾的回文子串,假设他们的左端点从左到右分别为$l_1,l_2,\ldots,l_k$,那么由于$[s_{l_1},s_{l_1+1},\ldots,s_{\left|s\right|}]$是回文串,那么对于$l_1\le p\le \left|s\right|$,都有$[s_p,s_{p+1},\ldots,s_{\left|s\right|}]=[s_{l_1},s_{l_1+1},\ldots,s_{l_1+\left|s\right|-p}]$,所以对于回文子串$s[s_{l_i},s_{l_i+1},\ldots,s_{\left|s\right|}]$,都有$s[s_{l_i},s_{l_i+1},\ldots,s_{\left|s\right|}=[s_{l_1},s_{l_1+1},\ldots,s_{l_1+\left|s\right|-l_i}]$,因此当$i\neq1$时,$s[s_{l_i},s_{l_i+1},\ldots,s_{\left|s\right|}$已经在$s’$中出现过,因此每次不同的回文串最多增加一个,因此结论对$s$仍然成立。

由数学归纳法可知定理1成立。
因此回文自动机的空间复杂度是$O(\left|s\right|)$级别的。

构造方法

我们使用增量法构造字符串$s$的回文自动机。
假设已经构造出了$s$的回文自动机,只需要在末尾增加一个字符$c$即可维护出$sc$的回文自动机。

定理2

以新加入的字符$c$为结尾的,未在$s$中出现过的回文子串最多只有$1$个,且为$sc$的最长回文后缀。

证明:由定理1的证明可得。

由定理2,每次只需要求出$sc$的最长回文后缀即可。
不妨设$[s_i,s_{i+1},\ldots,s_{\left|s\right|},c]$为$sc$的最长回文后缀,那么$[s_{i+1},s_{i+2},\ldots,s_{\left|s\right|}]$也是回文串。
故我们只需在$s$的$fail$链上找到一个长度最大的结点$t$,满足$s_{\left|s\right|-len_t}=c$,则$sc$的最长回文后缀就是$ctc$。

当然,对于$even$和$odd$我们不需要进行特判,经过其特殊定义,我们发现会暗中处理掉。

插入时,若不存在$ctc$对应的结点,我们需要新建一个结点。
如果新建了一个结点,我们还需要求出其后缀链接。
相当于在$t$对应结点的$fail$链上找出一个长度最长的结点$v$满足$s[\left|s\right|-len_v]=c$。
此处同样不需要考虑$even$和$odd$。

模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn];
Palindsome_Automaton() {init();}
void init() {
size=-1;
newnode(0); //even
newnode(-1); //odd
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
memset(child[now],0,sizeof(child[now]));
next[now]=0;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
child[p][data]=now;
}
last=child[p][data];
}
void build(string s) {
for(auto x:s)insert(x-'a');
}
} pam;

这种插入方法被称为基础插入法

基础插入法时间复杂度证明

我们使用势能分析分析基础插入法的时间复杂度。
我们只需要证明在$fail$链上寻找最长后缀回文的均摊时间复杂度是线性的。

设势能函数$\varphi(s)$为$s$的最长回文后缀的长度。
每次向上寻找最长回文后缀,$\varphi(s)$就会减少,每次插入的$\varphi(sc)\le \varphi(s)+1$,且$\varphi(s)\ge0$。
我们每次用势能支付寻找最长回文后缀的代价,不难发现在字符集为常数时,时间复杂度是$O(\left|s\right|)$的。

应用

回文自动机拓展

更多的回文自动机应用,未完待续。

进阶-使用回文自动机优化一类动规问题

参考本文

姥爷们赏瓶冰阔落吧~