2017-04-30

【算法笔记】回文自动机

本文为博主原创，未经许可不得转载

概述

回文自动机，简称$PAM$，可以识别母串$S$的所有回文子串

与后缀自动机相比，回文自动机简单易懂

我们知道解决回文串问题的一个强力算法$manacher$算法

事实上，根据我的理解，回文自动机与$manacher$算法的关系正如后缀自动机与后缀数组的关系一样

回文自动机关注的是整个串的回文性质，而$manacher$算法关注的是每个字符的回文性质

能用$manacher$算法解决的题目，大部分都可以用回文自动机解决

算法原理

变量的含义解释

now：当前状态
ch[i]：当前字符
len[i]：当前状态的最长回文串
fail[i]：失配边，与AC自动机的fail指针类似
size[i]：状态表示的回文串的数量
tr[now][i]：描述状态间的转移关系

构造过程

回文自动机的构造是在线的，这点与后缀自动机是一样的

首先建两个根结点，$0$表示长度为奇数的回文串，$1$表示偶数

然后令$fail[1]=fail[0]=1$

当加入一个字符$x$时，通过从当前状态$now$跳$fail$指针找到$x==ch[i-len[p]-1]$的状态$p$

若从状态$p$出发没有标号为$x$的边，则新建结点$np$，显然$len[np]=len[p]+2$

然后计算$np$结点的$fail$指针：$fail[np]=tr[fail[q]][x]$，$q$表示使得$ch[i-len[q]-1]==x$且$q!=p$的状态

我们可以通过跳$fail$指针的方法计找到状态$q$，然后令$tr[p][x]=np$即可

最后别忘了更新当前状态的位置$now$，令$size[now]++$即可

参考代码

struct node{
	int cnt,now,fail[MAXN],len[MAXN],size[MAXN],tr[MAXN][26];
	node() {cnt=1; fail[0]=fail[1]=1; len[1]=-1;}
	void extend(int x,int pos){
		int p=now; 
		while(ch[pos-len[p]-1]!=ch[pos]) p=fail[p];
		if(!tr[p][x]){
			int np=++cnt,q=fail[p]; len[np]=len[p]+2; 
			while(ch[pos-len[q]-1]!=ch[pos]) q=fail[q];  fail[np]=tr[q][x];  
			tr[p][x]=np;
		}
		now=tr[p][x]; size[now]++;
	}
}PAM;

例题选讲

【APIO2014】回文串

AC通道

这道题是用来练习回文自动机的模板题

建好回文自动机后，沿着$fail$指针更新$size$数组

因为在状态$i$中出现的回文串一定在状态$fail[i]$中出现过

套用那句揭示后缀自动机性质的老话：出现次数向父亲传递，接收串数从儿子获取

在回文自动机中也是适用的

然后用每个结点的$len[i]*size[i]$更新答案即可

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 300010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
int n,now,cnt(1),fail[MAXN],size[MAXN],len[MAXN],tr[MAXN][26];
ll ans;
char ch[MAXN];
void extend(int x,int pos){
	int p=now;
	while(ch[pos-len[p]-1]!=ch[pos])  p=fail[p];
	if(!tr[p][x]){
		int np=++cnt,q=fail[p];  len[np]=len[p]+2;
		while(ch[pos-len[q]-1]!=ch[pos]) q=fail[q]; fail[np]=tr[q][x];
		tr[p][x]=np;
	}
	now=tr[p][x];  size[now]++;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%s",ch+1);  n=strlen(ch+1);
	fail[0]=fail[1]=1;  len[1]=-1;
	for(int i=1;i<=n;++i)  extend(ch[i]-'a',i);
	for(int i=cnt;i;--i){
		size[fail[i]]+=size[i];
		cmax(ans,(ll)size[i]*len[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

【清华集训2011】最长双回文串

AC通道

首先建出回文自动机，然后统计以每个位置开始/结束的最长回文子串$L[i]$和$R[i]$

这两个数组的计算只需要在建立回文自动机的过程中更新即可：$R[pos]=L[pos-len[now]+1]=len[now]$

最后扫描一遍，用$L[i]+R[i+1]$更新答案即可

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
int n,ans,now,cnt(1),fail[MAXN],L[MAXN],R[MAXN],len[MAXN],tr[MAXN][26];
char ch[MAXN];
void extend(int x,int pos){
	int p=now;
	while(ch[pos-len[p]-1]!=ch[pos])  p=fail[p];
	if(!tr[p][x]){
		int np=++cnt,q=fail[p]; len[np]=len[p]+2;
		while(ch[pos-len[q]-1]!=ch[pos]) q=fail[q]; fail[np]=tr[q][x];
		tr[p][x]=np;
	}
	now=tr[p][x];  R[pos]=L[pos-len[now]+1]=len[now];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%s",ch+1);  n=strlen(ch+1);
	fail[0]=fail[1]=1;  len[1]=-1;
	for(int i=1;i<=n;++i)  extend(ch[i]-'a',i);
	for(int i=1;i<n;++i)  cmax(ans,R[i]+L[i+1]);
	printf("%d\n",ans);
	return 0;
}

参考文献

《回文树——处理一类回文串问题的强力工具》——poursoul 传送门

本文标题:【算法笔记】回文自动机

文章作者:chty

发布时间:2017年04月30日 - 10时51分

最后更新:2018年07月09日 - 20时19分

许可协议:本文为博主原创，未经许可不得转载。