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

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

0%

回文自动机学习笔记

发表于 更新于 分类于 Valine：

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

定义

一个回文自动机中包含两个结构：内部回文树（简称为回文树）和$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|)$的。

应用

回文自动机拓展

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

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

参考本文。

相关文章
姥爷们赏瓶冰阔落吧~