PAM(回文自动机)总结

其实只打了几个板子就没什么可说的

放个板子

struct node{
	int len,fail,nxt[26],sz;
#define len(k) t[k].len
#define fi(k) t[k].fail
#define c(p,x) t[p].nxt[x]
#define sz(k) t[k].sz
}t[500010];
int n,num,las,s[500010];
char a[500010];
inline void build(){ fi(0)=fi(1)=num=las=1; len(1)=-1; }
inline int Fail(int p){
	while(s[n]!=s[n-len(p)-1]) p=fi(p);
	return p;
}
inline int extend(cri x){
	cri p=Fail(las);
	if(!c(p,x)){
		len(++num)=len(p)+2;
		fi(num)=c(Fail(fi(p)),x);
		c(p,x)=num;
		sz(num)=sz(fi(num))+1;
	}
	return sz(las=c(p,x));
}

板子题:最长双回文串

改板子题:(Antisymmetry)

回文树题:双倍回文,(I Love Palindrome String)

原文地址:https://www.cnblogs.com/mikufun-hzoi-cpp/p/12098459.html