欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAM回文自动机学习小结

程序员文章站 2022-06-10 22:16:21
...

PAM


回文自动机

建议先学习AC自动机:AC自动机讲解超详细

回文自动机,顾名思义,用来处理回文串的自动机。

功能:

1.求 S S S串内本质不同的回文串个数

2.求 S S S串内本质不同的回文串出现次数

3.最小回文划分

4. S S S串中以下标 i i i结尾的最长回文串长度

回文树

PAM回文自动机学习小结

看看自己感悟一下。感觉特别形象,都不用解释了啊

还是稍微解释一下:

1.回文数上每一个节点代表了原串上出现过的一个本质不同回文子串,原串上的每一个回文子串都在回文树上有对应。回文树上每一个点代表的串都是回文串。

2.回文树分两部分,奇和偶,奇树上的点代表的回文串长度为奇数,偶树上的为偶

3.儿子节点代表串长度为父亲节点代表串长度 + 2 +2 +2

4.和 T r i e Trie Trie相似的其他性质,不说了

Fail指针

学过AC自动机的OIer们应该就很熟悉啦QwQ

F a i l Fail Fail指针含义:这个节点所代表的回文串的最长回文后缀

Trans指针

一般做许多PAM题目常用的东西

T r a n s Trans Trans指针含义:小于等于当前节点长度一半最长回文后缀

构建PAM

我们要维护以下信息

char s[maxn];		//原串
int fail[maxn];		//fail指针
int len[maxn];		//该节点表示的字符串长度
int tree[maxn][26];	//同Trie,指向儿子
int trans[maxn];	//trans指针
int tot,pre;		//tot代表节点数,pre代表上次插入字符后指向的回文树位置

其中 f a i l , l e n , t r e e , t r a n s fail,len,tree,trans fail,len,tree,trans为PAM上的信息

构建PAM的方法为增量,即一个一个加入字符构建PAM

奇树和偶树的根长度 l e n len len分别为 − 1 -1 1 0 0 0

设当前我们插入原串中 i i i位置的字符 u u u

那么以 i i i为结尾的最长回文串应该为(以 i − 1 i-1 i1为结尾的最长回文串 + u +u +u),并且那个回文串要满足前一个字符等于 u u u(不然就不是回文串了啊)

要找到那个点非常简单,不断从 p r e pre pre开始跳 f a i l fail fail,直到找到一个满足 s [ i − l e n [ x ] − 1 ] = = u s[i-len[x]-1]==u s[ilen[x]1]==u 的节点 F a i l Fail Fail ,那么从 F a i l Fail Fail建一个 u u u儿子即可以表示新的回文串。

新点的 f a i l fail fail怎么求呢。

明显为从 p r e pre pre开始跳 f a i l fail fail,找到**{** [第二个(满足 s [ i − l e n [ x ] − 1 ] = = u s[i-len[x]-1]==u s[ilen[x]1]==u) 的节点 x x x **]**的 u u u儿子 }

也就是从 F a i l Fail Fail开始跳 f a i l fail fail,找到**{** [第一个(满足 s [ i − l e n [ x ] − 1 ] = = u s[i-len[x]-1]==u s[ilen[x]1]==u) 的节点 x x x **]**的 u u u儿子 }

跳到根记得判断

特别提醒:节点 1 1 1为奇根,节点 0 0 0为偶根, f a i l [ 0 ] = 1 fail[0]=1 fail[0]=1 , l e n [ 1 ] = − 1 len[1]=-1 len[1]=1

时间复杂度证明参考OIwiki:OIwiki-PAM

放代码理解:

int getfail(int x,int i){		//从x开始跳fail,满足字符s[i]的节点
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
void insert(int u,int i){
	int Fail=getfail(pre,i);		//找到符合要求的点
	if(!tree[Fail][u]){		//没建过就新建节点
		len[++tot]=len[Fail]+2;	//长度自然是父亲长度+2
		fail[tot]=tree[getfail(fail[Fail],i)][u];	//fail为满足条件的次短回文串+u
		tree[Fail][u]=tot;		//认儿子
	}
	pre=tree[Fail][u];		//更新pre
}

至于 t r a n s trans trans维护也和 f a i l fail fail差不多

根据 t r a n s trans trans的定义去推一下怎么搞吧

放一下完整代码:

char s[maxn];		//原串
int fail[maxn];		//fail指针
int len[maxn];		//该节点表示的字符串长度
int tree[maxn][26];	//同Trie,指向儿子
int trans[maxn];	//trans指针
int tot,pre;		//tot代表节点数,pre代表上次插入字符后指向的回文树位置
int getfail(int x,int i){		//从x开始跳fail,满足字符s[i]的节点
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
int gettrans(int x,int i){
	while(((len[x]+2)<<1)>len[tot]||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
void insert(int u,int i){
	int Fail=getfail(pre,i);		//找到符合要求的点
	if(!tree[Fail][u]){		//没建过就新建节点
		len[++tot]=len[Fail]+2;	//长度自然是父亲长度+2
		fail[tot]=tree[getfail(fail[Fail],i)][u];	//fail为满足条件的次短回文串+u
		tree[Fail][u]=tot;		//指儿子
		if(len[tot]<=2)trans[tot]=fail[tot];	//特殊trans
		else{
			int Trans=gettrans(trans[Fail],i);	//求trans
			trans[tot]=tree[Trans][u];
		}
	}
	pre=tree[Fail][u];		//更新pre
}

应用

P5496【模板】回文自动机(PAM)

求第 i 个整数表示原串以第 i 个字符结尾的回文子串个数,强制在线

明显:一个回文串的答案等于其最长回文后缀的答案 + 1 +1 +1 (这超好理解的吧

那就在多维护一个信息 a n s ans ans表示答案,新建节点时更新即可

ans[tot]=ans[fail[tot]]+1;

答案为lastans=ans[pre];

代码:

#include<bits/stdc++.h>
#define maxn 510001
using namespace std;
char s[maxn];
int fail[maxn],len[maxn],ans[maxn],trie[maxn][26];
int pre,slen,lastans,tot;
int getfail(int x,int i){
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
int main(){
	scanf("%s",s);slen=strlen(s);
	fail[0]=1;len[1]=-1;tot=1;
	for(int i=0;i<slen;i++){
		if(i>=1)s[i]=(s[i]-97+lastans)%26+97;
		int u=s[i]-'a';
		int Fail=getfail(pre,i);
		if(!trie[Fail][u]){
			fail[++tot]=trie[getfail(fail[Fail],i)][u];
			trie[Fail][u]=tot;
			len[tot]=len[Fail]+2;
			ans[tot]=ans[fail[tot]]+1;
		}
		pre=trie[Fail][u];
		lastans=ans[pre];
		printf("%d ",lastans);
	}
	return 0;
}

P4287[SHOI2011]双倍回文

学好 t r a n s trans trans指针,秒切此题

明显:当存在 i i i满足 l e n [ t r a n s [ i ] ] ∗ 2 = = l e n [ i ] len[trans[i]]*2==len[i] len[trans[i]]2==len[i]并且满足题意中 l e n [ t r a n s [ i ] ] len[trans[i]]%2==0 len[trans[i]]即为符合题意的串,取最长即可。

代码:真·模板

#include<bits/stdc++.h>
#define maxn 510001
using namespace std;
char s[maxn];		//原串
int fail[maxn];		//fail指针
int len[maxn];		//该节点表示的字符串长度
int tree[maxn][26];	//同Trie,指向儿子
int trans[maxn];	//trans指针
int tot,pre;		//tot代表节点数,pre代表上次插入字符后指向的回文树位置
int getfail(int x,int i){		//从x开始跳fail,满足字符s[i]的节点
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
int gettrans(int x,int i){
	while(((len[x]+2)<<1)>len[tot]||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
void insert(int u,int i){
	int Fail=getfail(pre,i);		//找到符合要求的点
	if(!tree[Fail][u]){		//没建过就新建节点
		len[++tot]=len[Fail]+2;	//长度自然是父亲长度+2
		fail[tot]=tree[getfail(fail[Fail],i)][u];	//fail为满足条件的次短回文串+u
		tree[Fail][u]=tot;		//指儿子
		if(len[tot]<=2)trans[tot]=fail[tot];	//特殊trans
		else{
			int Trans=gettrans(trans[Fail],i);	//求trans
			trans[tot]=tree[Trans][u];
		}
	}
	pre=tree[Fail][u];		//更新pre
}
int slen,ans;
int main(){
	scanf("%d",&slen);
	scanf("%s",s);
	fail[0]=1;len[1]=-1;tot=1;
	for(int i=0;i<slen;i++)insert(s[i]-'a',i);
	for(int i=2;i<=tot;i++){
		if(len[trans[i]]*2==len[i]&&len[trans[i]]%2==0)
		ans=max(ans,len[i]);
	}
	printf("%d\n",ans);
	return 0;
}

P4555[国家集训队]最长双回文串

题目描述:

顺序和逆序读起来完全一样的串叫做回文串。比如`acbca`是回文串,而`abc`不是(`abc`的顺序为`abc`,逆序为`cba`,不相同)。

输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

简单PAM题

题解:

正着建一棵PAM, a [ i ] a[i] a[i]记录当前位置 i i i结尾最长回文串长度

反着建一棵PAM, b [ i ] b[i] b[i]记录当前位置 i i i结尾最长回文串长度

a [ i ] + b [ i + 1 ] a[i]+b[i+1] a[i]+b[i+1]即为以 i i i为分界的双回文串

a [ i ] + b [ i + 1 ] a[i]+b[i+1] a[i]+b[i+1]最大值即为答案

代码:封装版PAM

#include<bits/stdc++.h>
#define maxn 510001
using namespace std;
char s[maxn];
int slen,a[maxn],b[maxn],ans;
struct PAM{
	int fail[maxn],len[maxn],trie[maxn][26];
	int tot,pre;
	void init(){fail[0]=1;len[1]=-1;tot=1;pre=0;}
	int getfail(int x,int i){
		while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
		return x;
	}
	void insert(int u,int i){
		int Fail=getfail(pre,i);
		if(!trie[Fail][u]){
			fail[++tot]=trie[getfail(fail[Fail],i)][u];
			trie[Fail][u]=tot;
			len[tot]=len[Fail]+2;
		}
		pre=trie[Fail][u];
	}
}A,B;
int main(){
	scanf("%s",s);slen=strlen(s);A.init();B.init();
	for(int i=0;i<slen;i++)A.insert(s[i]-'a',i),a[i]=A.len[A.pre];
	reverse(s,s+slen);		//翻转
	for(int i=0;i<slen;i++)B.insert(s[i]-'a',i),b[slen-i-1]=B.len[B.pre];
	for(int i=0;i<slen-1;i++)ans=max(ans,a[i]+b[i+1]);
	printf("%d\n",ans);
	return 0;
}

P4762[CERC2014]Virus synthesis

PAM好题,请好好思考

题意:

初始有一个空串,利用下面的操作构造给定串 S S S

1、串开头或末尾加一个字符

2、串开头或末尾加一个该串的逆串

求最小化操作数, ∣   S ∣ ≤ 1 0 5 ∣\ S∣≤10^5  S105

题解:

PAM上dp

To be continue……

上一篇: 如果编程语言是船

下一篇: 2018/6/7