处理回文串的利器。
0.结构
回文自动机 PAM 和其它自动机类似。回文自动机包含一个串的所有回文子串。回文树也是由转移边 fail 指针和后缀链接（fail 指针）组成，每个节点都可以代表一个回文子串。转移边与节点形成回文树。
回文串长度分为奇数和偶数，我们显然应该分开处理。一种方法是尝试按照 Manacher 在字符之间插入分隔符，将偶数回文串转化为奇数回文串；另一种更好的方法是我们直接建两棵回文树，也就是建两个根，一个奇根一个偶根。
1.构造
相对于后缀自动机简单了很多。首先是两个初始状态，也就是我们上面提到的奇根和偶根，分别代表长度为 $-1$ 和 $0$ 的字符串。偶根的 fail 指针指向奇根，奇根不可能失配，所以不关心奇根的 fail 指针。
过程中，类似后缀自动机，我们尝试增量构造。考虑已经构造完前 $p-1$ 个字符的回文自动机之后，我们从上一个字符（也就是 $p-1$）对应的结尾的最长回文子串对应的节点开始，不断沿 fail 指针移动，直到 $s_{p-len-1}=s_{p}$。设此时移动到 $a$。此时相当于找到一个回文串，没有这个节点，就需要新建。
求该节点的 fail 指针也是同理，从 $a$ 开始继续跳，直到再次满足 $s_{p-len-1}=s_{p}$，也就是最长回文后缀。这个节点一定存在（考虑回文的性质）。
容易知道，整个过程时间复杂度为 $\mathcal O(n)$。
一些别的理解：
对于一个回文串 $s$，将其长度为 $\lceil\frac{|s|}{2}\rceil$ 的后缀称为其半串。回文树可以看作是所有回文子串对应的半串的 Trie（但对长度为奇数和偶数的回文串有特殊的标识分开），于是我们可以构造它的 ACAM。这样构造出的自动机结构称为回文自动机，类似可以定义失配指针，失配树。
P5496 【模板】回文自动机（PAM）
Code
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
45
46
47
48
49
50
51
52
53
54
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=5e5+10,C=26+5;
namespace PAM
{
int n,tot;
char s[N];
int fail[N],len[N],tr[N][C];
int cnt[N];
int newnode(int l)
{
tot++;
memset(tr[tot],0,sizeof(tr[tot]));
len[tot]=l;
fail[tot]=cnt[tot]=0;
return tot;
}
int getfail(int pos,int x)
{
while(s[pos-len[x]-1]!=s[pos])x=fail[x];
return x;
}
void build()
{
tot=-1;
s[0]='$';
fail[newnode(0)]=newnode(-1);
n=strlen(s+1);
for(int i=1,last=0;i<=n;i++)
{
s[i]=(s[i]-'a'+cnt[last])%26+'a';
int now=getfail(i,last),c=s[i]-'a';
if(!tr[now][c])
{
int x=newnode(len[now]+2);
fail[x]=tr[getfail(i,fail[now])][c];
tr[now][c]=x;
}
last=tr[now][c];
cnt[last]=cnt[fail[last]]+1;
printf("%d ",cnt[last]);
}
}
};
int main()
{
scanf("%s",PAM::s+1);
PAM::build();
return 0;
}
|
2.应用
2.1 本质不同回文子串个数
由线性状态数的证明，容易知道一个串的本质不同回文子串个数等于回文树的状态数（排除奇根和偶根两个状态）。
2.2 回文子串出现次数
建出回文树，使用类似后缀自动机统计出现次数的方法。
由于回文树的构造过程中，节点本身就是按照拓扑序插入，因此只需要逆序枚举所有状态，将当前状态的出现次数加到其 fail 指针对应状态的出现次数上即可。
例题：P3649 [APIO2014] 回文串。
Code
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=3e5+10,C=26+5;
namespace PAM
{
int n,tot;
char s[N];
int fail[N],len[N],tr[N][C];
int cnt[N];
int newnode(int l)
{
tot++;
memset(tr[tot],0,sizeof(tr[tot]));
len[tot]=l;
fail[tot]=cnt[tot]=0;
return tot;
}
int getfail(int pos,int x)
{
while(s[pos-len[x]-1]!=s[pos])x=fail[x];
return x;
}
void build()
{
tot=-1;
s[0]='$';
fail[newnode(0)]=newnode(-1);
n=strlen(s+1);
for(int i=1,last=0;i<=n;i++)
{
int now=getfail(i,last),c=s[i]-'a';
if(!tr[now][c])
{
int x=newnode(len[now]+2);
fail[x]=tr[getfail(i,fail[now])][c];
tr[now][c]=x;
}
last=tr[now][c];
cnt[last]++;
}
}
ll solve()
{
ll ans=0;
for(int i=tot;~i;i--)ans=max(ans,1ll*len[i]*cnt[i]),cnt[fail[i]]+=cnt[i];
return ans;
}
};
int main()
{
scanf("%s",PAM::s+1);
PAM::build();
printf("%lld\n",PAM::solve());
return 0;
}
|
2.3 最小回文划分
给定一个字符串 $s(1\le |s| \le 10^5)$，求最小的 $k$，使得存在 $s_1,s_2,\dots,s_k$，满足 $s_i(1\le i \le k)$ 均为回文串，且 $s_1,s_2, \dots ,s_k$ 依次连接后得到的字符串等于 $s$。
考虑暴力做法，我们建出回文自动机以找出所有回文串。设计状态 $f_i$ 表示 $s[1,i]$ 最少多少个回文串划分，容易得到转移 $f_i=\min f_j+1$，其中 $s[j+1,i]$ 为回文串。这样时间复杂度是 $\mathcal O(n^2)$。
接下来我们介绍一些引理，并且对上述暴力算法进行优化：
引理一
$t$ 是回文串 $s$ 的后缀，$t$ 是 $s$ 的 border 当且仅当 $t$ 是回文串。
引理二
$t$ 是串 $s$ 的 border ($|s|\le 2|t|$)，$s$ 是回文串当且仅当 $t$ 是回文串。
引理三
$t$ 是回文串 $s$ 的 border，则 $|s|-|t|$ 是 $s$ 的周期，$|s|-|t|$ 为 $s$ 的最小周期，当且仅当 $t$ 是 $s$ 的最长回文真后缀。
引理四
$x$ 是一个回文串，$y$ 是 $x$ 的最长回文真后缀，$z$ 是 $y$ 的最长回文真后缀。令 $u,v$ 分别为满足 $x=uy,y=vz$ 的字符串，则有下面三条性质
$|u| \ge |v|$；
如果 $|u| > |v|$，那么 $|u| > |z|$；
如果 $|u| = |v|$，那么 $u=v$。
推论
$s$ 的所有回文后缀按照长度排序后，可以划分成 $\log |s|$ 段等差数列。
更一般地，这个可以通过 Border 理论得到。
优化
我们尝试利用等差数列的性质，将相同等差数列中的答案进行压缩。
我们寻找所有回文串的过程就是不断地跳 fail 指针，过程中将依次经过 $\log n$ 个等差数列。我们维护该等差数列的中 Border 对应位置的答案的 $\min$。加上当前字符之后，若 $x$ 与 $fail[x]$ 在同一个等差数列中，那么相当于对应的等差数列向右移动 公差 个位置 。唯一比 $fail[x]$ 对应的维护的 $\min$ 多出来的位置就是原来 等差数列的首项 再加上 公差，我们把这个位置算上即可。过程中我们只需要一直跳首项即可，最多跳 $\log n$ 次。时间复杂度为 $\mathcal O(n\log n)$。
例题：CF932G Palindrome Partition
考虑将原字符串进行按照 $s_1 s_n s_2 s_{n-1}\cdots s_{\frac{n}{2}}s_{\frac{n}{2}+1}$ 拼接，这样就转化为，将其划分为若干个偶回文串的方案数。于是跟上面几乎一样，不过我们只在偶数位置计数就好了。
可以说是因为这一道题去学了回文自动机。
Code
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=1e6+10,C=26+5,mod=1e9+7;
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
namespace PAM
{
int n,tot;
char s[N];
int fail[N],len[N],tr[N][C];
int slink[N],diff[N];
int f[N],g[N];
int newnode(int l)
{
tot++;
memset(tr[tot],0,sizeof(tr[tot]));
len[tot]=l;
fail[tot]=0;
return tot;
}
int getfail(int pos,int x)
{
while(s[pos-len[x]-1]!=s[pos])x=fail[x];
return x;
}
void build()
{
tot=-1;
s[0]='$';
fail[newnode(0)]=newnode(-1);
n=strlen(s+1);
f[0]=1;
for(int i=1,last=0;i<=n;i++)
{
int now=getfail(i,last),c=s[i]-'a';
if(!tr[now][c])
{
int x=newnode(len[now]+2);
fail[x]=tr[getfail(i,fail[now])][c];
tr[now][c]=x;
diff[x]=len[x]-len[fail[x]];
if(diff[x]==diff[fail[x]])slink[x]=slink[fail[x]];
else slink[x]=fail[x];
}
last=tr[now][c];
for(int x=last;x>1;x=slink[x])
{
g[x]=f[i-len[slink[x]]-diff[x]];
if(diff[x]==diff[fail[x]])upd(g[x],g[fail[x]]);
if(i&1)continue;
upd(f[i],g[x]);
}
}
}
};
int n;
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
if(n&1)return puts("0");
for(int i=1,tot=0;i<=(n>>1);i++)PAM::s[++tot]=s[i],PAM::s[++tot]=s[n-i+1];
PAM::build();
printf("%d\n",PAM::f[n]);
return 0;
}
|