[模板] 回文树/回文自动机 && BZOJ3676:[Apio2014]回文串

回文树/回文自动机

放链接:

回文树或者回文自动机，及相关例题 - F.W.Nietzsche - 博客园

状态数的线性证明

并没有看懂上面的证明,所以自己脑补了一个...

引理: 每一个回文串都是字符串某个前缀的最长回文后缀.

证明. 考虑一个回文串在字符串中第一次出现的位置, 记为 $S_{p_1 ... p_2}$, 它一定是 $S_{1 ... p_2}$的最长回文后缀.

否则, 如果有 $S_{p_3 ... p_2} (p_3<p_1)$ 也为回文串, 那么由于回文, $S_{p_3 ... p_3-p_2+p_1} = S_{p_1 ... p_2}$, $S_{p_1 ... p_2}$并不是它第一次出现的位置.矛盾.

因而命题得证.

而每个点的最长回文后缀是唯一的, 因此$S$最多只有$|S|$个不同的回文子串.

引理的推论. 一个回文串 $\leftrightarrow$ 某个串的最长回文子串 && 某个串的最长回文子串的回文后缀.

关于fail指针

fail指针指向的是一个节点代表的回文串的最长回文后缀.

在build时, 它也可以理解为以某个点为结尾的次长回文后缀.

Code

const int ssz=300050;

ll n;

char s[ssz];

struct te{int l,fail,cnt,ch[27];}tree[ssz]{{0,1},{-1,1}};

int pt=1,rt0=0,rt1=1;

#define ch(p,c) tree[p].ch[c]

#define fail(p) tree[p].fail

int newnd(){return ++pt;}

int getfail(int p,int i){

	while(s[i-1-tree[p].l]!=s[i])p=fail(p);

	return p;

}

void build(){

	int p,q,last=0;

	rep(i,1,n){

		p=getfail(last,i);

		if(ch(p,s[i])==0){

			q=newnd();

			tree[q].l=tree[p].l+2,fail(q)=ch(getfail(fail(p),i),s[i]);

			ch(p,s[i])=q;

		}

		last=ch(p,s[i]);

		++tree[last].cnt;

	}

}

应用

枚举所有回文子串

dfs即可.

拓扑序

显然拓扑序就是 ${ 1, 2, \cdots, n } $.

求字符串出现次数

加入每个字符后, ++cnt[last];;

然后逆拓扑序dp, cnt[fa(p)] += cnt[p].

cnt[p] 即为回文串 $p$ 出现次数.

详见下面的题.

每个节点长度 $\le \frac {len}2$ 的回文后缀

和维护fail指针大体类似, 加上限制条件即可.

详见代码.

其中tree[p].tr表示的是 $p$ 节点长度 $\le \frac {len}2$ 的回文后缀

struct tnd{int l,fi,ch[csz],tr;}tree[ssz];

#define ch(p,c) tree[p].ch[c]

#define fail(p) tree[p].fi

#define trl(p) tree[p].l

#define trtr(p) tree[p].tr

int rt0=0,rt1=1,pt=1;

int getfail(int p,int i){

	while(s[i-1-trl(p)]!=s[i])p=fail(p);

	return p;

}

void build(){

	int p,q,last=0;

	rep(i,1,n){

		p=getfail(last,i);

		if(ch(p,s[i])==0){

			q=++pt;

			trl(q)=trl(p)+2,fail(q)=ch(getfail(fail(p),i),s[i]);

//get tr(p) start

			if(trl(q)<=1)trtr(q)=fail(q);

			else{

				int z=trtr(p);

				while(s[i-1-trl(z)]!=s[i]||(trl(z)+2)*2>trl(q))z=fail(z);

				trtr(q)=ch(z,s[i]);

			}

//end

			ch(p,s[i])=q;

		}

		last=ch(p,s[i]);

	}

}

例题

BZOJ3676:[Apio2014]回文串

求回文串长度*出现次数的最大值.

板子题.

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

using namespace std;

#define rep(i,l,r) for(register int i=(l);i<=(r);++i)

#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)

#define il inline

typedef double db;

typedef long long ll;

//---------------------------------------

const int ssz=300050;

ll n,ans=0;

char s[ssz];

struct te{int l,fail,cnt,ch[27];}tree[ssz]{{0,1},{-1,1}};

int pt=1,rt0=0,rt1=1;

#define ch(p,c) tree[p].ch[c]

#define fail(p) tree[p].fail

int newnd(){return ++pt;}

int getfail(int p,int i){

	while(s[i-1-tree[p].l]!=s[i])p=fail(p);

	return p;

}

void build(){

	int p,q,last=0;

	rep(i,1,n){

		p=getfail(last,i);

		if(ch(p,s[i])==0){

			q=newnd();

			tree[q].l=tree[p].l+2,fail(q)=ch(getfail(fail(p),i),s[i]);

			ch(p,s[i])=q;

		}

		last=ch(p,s[i]);

		++tree[last].cnt;

	}

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0);

	cin>>(s+1);

	n=strlen(s+1);

	rep(i,1,n)s[i]-='a'-1;

	build();

	repdo(i,pt,2){

		tree[fail(i)].cnt+=tree[i].cnt;

		ans=max(ans,(ll)tree[i].cnt*tree[i].l);

	}

	cout<<ans<<'\n';

	return 0;

}

秒客网