回文自动机

回文自动机

回文自动机(PAM)

回文自动机是一种高效处理回文串相关操作的数据结构,这一节我们专门描述回文自动机以及其扩展应用。

定理:一个字符串中的本质不同回文子串只有 O(n) 个。

证明:考虑 Manacher 的过程,每次复制一个区间暴力扩展是 O(n) 的,而复制的区间的回文串都在之前出现过,所以定理得证。

构建

首先,明确一下回文自动机和回文树上的定义:

回文自动机的一个节点 p 代表一个字符串 S,从它经过一条转移边 c 到达字符串为 cSc 的节点。

回文树上的一个节点 p 唯一对应回文自动机上的一个节点(双射),p 的父亲 fpp 所代表字符串的最长回文后缀处在的节点。

任意一个节点都唯一对应一个回文子串,本质相同的回文子串对应相同的节点。

存储的时候,我们只在节点上存储对应回文子串的长度,如果要得知具体的子串,可以记录 endpos 然后递归搜索即可。

于是,我们发现了一个问题,回文子串具有奇数和偶数长度,这两个长度在回文自动机上一定是不相交的,解决方法便是初始状态建立两个根,奇根和偶根,其中偶根在回文树上的父亲是奇根,奇根所代表的字符串长度为 1,偶根代表的字符串长度为 0

考虑加入一个字符 ch,回文自动机和回文树会发生什么变化,首先我们需要记录加入之前,这个串的最长回文后缀,这是简单的,然后考虑新的串的最长回文后缀。

设原来的最长回文后缀代表节点为 p,那么我们需要顺着 p 在回文树上一直跳转,直到 p 之前的第一个字符等于 ch,这个时候,新的串的最长回文后缀就是 pamp,ch,特别的,如果没有这个节点,需要新建。

然后考虑新建的节点在回文树上的父亲是什么,然后我们继续顺着 p 在回文树上跳转,直到找到另外一个 p 之前的第一个字符等于 ch,这个时候 pamp,ch 就是新建的节点在回文树上的父亲,这个节点是一定存在的,因为它是跳转之前的那个 p 的一个真前缀。

如果找不到,就令新建的节点在回文树上的父亲为偶根,即长度 0 的节点即可,判断是否相等可以判断为 silenp1=si,这个时候,奇根也起作用了,因为 si(1)1 一定等于 si,所以第一步如果没有匹配上,它就一定会成为奇根的 pamch

构建过程如下图所示,图片源自 OI-wiki:

时间复杂度:当前节点(最长回文后缀)在回文树上的深度每次最多增加 1,所以构建过程为 O(n)

这个回文自动机只支持往后添加字符,考虑如何支持往前添加字符,因为如果 st 的回文后缀(t 也是回文串),那么 s 也是 t 的回文前缀,所以往前添加字符也可以用这个回文树和回文自动机。

不过需要处理最长回文前缀,注意到在后面添加字符的时候这个东西不会改变;在前面添加字符的时候最长回文后缀也不会改变,除非整个串是回文串,特判一下就可以了。

下面给出支持后端插入的代码,以 P3649 APIO2014 回文串 为例,这道题只需要统计每个回文串出现的次数就可以了,比较简单,套路就是在每个前缀的最长回文后缀那里打一个标记,然后遍历一遍回文树上传标记数量就可以了。

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
#include<bits/stdc++.h>
#define ll long long
#define N 300005
using namespace std;
char s[N];
ll root_1=1,root0=2,n,i,fath[N],pam[N][26],now=1,tot=2,ne[N],la[N],to[N],et,son[N],ans,len[N];
inline void merge(ll x,ll y){et++,ne[et]=la[x],la[x]=et,to[et]=y;}
inline void insert(ll x,ll id){
while(s[id]!=s[id-len[now]-1]) now=fath[now];
if(!pam[now][x]) pam[now][x]=++tot,len[tot]=len[now]+2;
ll temp = pam[now][x];
now=fath[now];
while(now&&s[id]!=s[id-len[now]-1]) now=fath[now];
if(now) fath[temp]=pam[now][x];
else fath[temp]=root0;
now=temp;
}
inline void dfs(ll x){
for(ll i=la[x];i;i=ne[i]) dfs(to[i]),son[x]+=son[to[i]];
ans=max(ans,son[x]*len[x]);
}
int main(){
fath[2]=1,len[1]=-1;
ios::sync_with_stdio(false);
cin>>(s+1),n=strlen(s+1);
for(i=1;i<=n;i++) insert(s[i]-'a',i),son[now]++;
for(i=2;i<=tot;i++) merge(fath[i],i);
dfs(1);
cout<<ans<<endl;
return 0;
}

其他性质

我们从处理一个串的回文划分数量开始说起。

回文划分,即划分成若干个回文子串的数量,例如 S=abba,那么它有 3 种回文划分方式。

暴力统计的话是 O(n2) 的,我们这里主要讨论的是利用回文后缀的性质的 O(nlogn) 做法。

暴力做法公式:fi=i1j=0fjpj+1,i,其中 pl,r=1/0 表示 S[l,r] 是否为回文串。

定理:一个回文串的所有回文后缀可以按照长度划分成 O(logn) 段。

证明:因为一个回文串的回文后缀一定是这个回文串的 border,问题就变成了一个回文串的 border 可以按照长度划分为 O(logn) 段,然后用定理“任意字符串的 border 可以按照长度划分成 O(logn) 段”即可。

于是我们考虑知道了 f1i1 的值,添加一个字符之后计算 fi 的值。

首先我们需要在回文自动机上多维护两个值 diffxslinkx,第一个表示 lenxlenfax,第二个表示 x 的祖先中离 x 最近的节点满足 diffxdiffuu,此时 slinkx=u,根据上面的定理从 x 一直跳 slinkx 可以跳不超过 log 步到达根节点,这里规定根节点为偶根,奇根只会带来不必要的讨论,故舍弃它。

此外还有一个转移数组 gx 表示所有 uxslinkx(不包含 slinkx)的 fendposlenu 的和,其中 endposx(也是所有 u)在原串中出现的最晚的位置。(x 是当前等差数列最长的字符串 g 才有值,否则 g 的值有误)

用图片来表达就是下面这个样子(图片源于 OI-wiki):

其中 gx 为所有橙色位置的 f 的和,考虑添加之后如何转移,我们发现添加一个字符之前 fax 是其所在等差数列中最长的字符串,否则 x 一定不是所在等差数列中最长的字符串(可以往左扩展 diffx 步),所以 gfax 是正确的,存储了蓝色位置的 f 值,我们发现 gx 相较于 gfax 多了一个 fxlenslinkxdiffx,加上即可。

每次新增一个字符都暴力跳当前最长后缀节点的 slink,更新 g,然后每次都累加到当前 fi 中即可,时间复杂度为严格 O(nlogn)

补充说明:建立回文自动机的时候也可以像这样做到单次时间复杂度不超过 log,总和不超过 O(n) 的做法,但是一般不常用,作为技巧积累下来。依据这个性质,还可以完成强制在线的询问区间本质不同回文子串数量,这里就不展开讲了。

例题:Codeforces 932G Palindrome Partition

s0sn1s1sn2 的偶回文划分数,基本上是模板题,只在 fi,imod2=0 的地方存储值即可。

下面给出一份参考代码:

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
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 1000005
using namespace std;
char s[N],t[N];
ll root_1=1,root0=2,n,i,j,fath[N],pam[N][26],now=1,tot=2,len[N],dp[N],slink[N],g[N],diff[N];
inline void insert(ll x,ll id){
while(s[id]!=s[id-len[now]-1]) now=fath[now];
if(!pam[now][x]) pam[now][x]=++tot,len[tot]=len[now]+2;
ll temp = pam[now][x];
now=fath[now];
while(now&&s[id]!=s[id-len[now]-1]) now=fath[now];
if(now) fath[temp]=pam[now][x];
else fath[temp]=root0;
now=temp,diff[now]=len[now]-len[fath[now]];
if(diff[now]==diff[fath[now]]) slink[now]=slink[fath[now]];
else slink[now]=fath[now];
}
int main(){
fath[2]=1,len[1]=-1,diff[2]=1;
ios::sync_with_stdio(false);
cin>>(s+1),n=strlen(s+1);
for(i=1;i<=n;i++){
if(i&1) t[i]=s[(i+1)/2];
else t[i]=s[n-i/2+1];
}
for(i=1;i<=n;i++) s[i]=t[i];
if(n&1){
cout<<0<<endl;
return 0;
}
dp[0]=1;
for(i=1;i<=n;i++){
insert(s[i]-'a',i);
for(j=now;j>1;j=slink[j]){
g[j]=dp[i-len[slink[j]]-diff[j]];
if(diff[j]==diff[fath[j]]) g[j]=(g[j]+g[fath[j]])%mod;
if(i%2==0) dp[i]=(dp[i]+g[j])%mod;
}
}
cout<<dp[n]<<endl;
return 0;
}