NanoApe's Blog

既是咸鱼又是辣鸡

【字符串】Palindromic Tree & Manacher

NanoApe posted @ 2015年8月17日 17:32 in 蒟蒻不撕烤智熵何来 , 594 阅读

嘛回文。


先说说回文树。

Orz VictorWonder写的论文:http://victorwonder.blog.uoj.ac/blog/146

其实就是两棵树(分别代表奇偶长度的回文串)+回文后缀链咯,在线维护什么的不难玩

介绍的话上面的博文也写的很清楚了,想想应用?

论文里面说能把两个树合并到一起,就能动态化?弄个树形DP?弄个LCT?妈呀构造不出来。。。

自己后来又想了几个模型,在这里写不下就不写了。

int now, tmp, last=0;
cn=1; len[0]=0; len[1]=-1; fail[0]=fail[1]=1; last=0;
//Init
rep(i, 1, L)
{
	for(now=last; s[i-len[now]-1]!=s[i]; now=fail[now]);
	if (!c[now][s[i]-'a']) 
	{
		for(tmp=fail[now]; s[i-len[tmp]-1]!=s[i]; tmp=fail[tmp]);

		//New Node(Array_Fail Before Array_C)
		fail[++cn]=c[tmp][s[i]-'a'];
		c[now][s[i]-'a']=cn;

		//Cal Data
		len[cn]=len[now]+2; d[cn]=d[fail[cn]]+1;
	}
	last=c[now][s[i]-'a'];
	cnt[last]++;
}

几个应用:

清澄1280-BZOJ2565

清澄1255-BZOJ2160

清澄1393

HDU5421


对于回文子串,回文树能搞的Manacher也能搞,Manacher能搞的回文树有时也不行(在我这个蒟蒻看来的啊。。。

换句话说,有些题回文树很容易解决,Manacher却比较麻烦;有些题则颠倒过来

所以,Manacher其实也是要很熟练的。。。

rep(i, 0, l-1) s[i*2+1]='$', s[i*2+2]=c[i];
s[0]='#'; s[l*2+1]='$';
ans=o=p=0;
rep(i, 1, l*2+1)
{
	k[i] = i<p ? min(p-i, k[o*2-i]) : 1;
	while (s[i+k[i]] == s[i-k[i]]) k[i]++;
	if (i+k[i]>p) p=i+k[i], o=i;
}

然后就来看各种回文题了:

BZOJ2342 双倍回文

做出Manacher后,枚举中心和次中心,然后加个最优性剪枝可过

 

 

涉及论文:《回文树的构建及其应用》《浅谈回文子串问题》


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter