回文树总结 by dsl

发布于 2018-02-02  402 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:回文树总结 by dsl

回文树总结

引入

对于一般的字符串问题,我们拥有处理它们的强大工具——后缀数组,后缀树,后缀自动机。
但对于一类特殊的关于回文串的字符串问题,我们也有一种强大的工具——回文树(由Mikhail Rubinchik发明,在Petrozavodsk Summer Camp 2014上首次提出来)。

回文树

安利我的博客「学习笔记」回文树/回文自动机(Palindromic Tree)
和一篇论文国家集训队2017论文集《回文树及其应用》——翁文涛。

例题

A.[BZOJ2565]最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

2≤|S|≤10^5

Solution

正反建两个回文树,同时计算出\(s_{1..i}\)的最长回文后缀和\(s_{i+1..|s|}\)的最长回文前缀。
取和的\(max\)即可。

B.[SHOI2011]双倍回文

Description

题面

Solution

直接构造出回文树,然后在\(fail\)树上dfs。一个回文串是双倍回文串的条件是长度是4且父亲中有长度为其一半的回文串即可。

C.[51nod]Clarke and string

D.[省队集训2013day7T1]str

Description

求一个串第\(k\)小的回文子串。

字符串比较方式如下(与一般的比较方式不完全相同)

\(|s|\leqslant 10^5\)

Solution

方法1:

字符串比较的方式为先比较长度,然后比较字符。所以可以直接在回文树上bfs。

方法2(std):
Markdown

从这道题我们可以看出回文树在处理回文串的优越性。

E.[省队集训2015day1T1]字符串合成

Description

给定四种对字符串 S 的操作:
(1) push_back( P ):在 S 后连接一个字符串 P,即 S = S + P,代价为| P |;
(2) push_front( P ):在 S 前连接一个字符串 P,即 S = P + S,代价为| P |;
(3) symmetry_back( ):将 S 翻转后连接在 S 之后,即 S = S + rev(S),代价为 1;
(4) symmetry_front( ):将 S 翻转后连接在 S 之前,即 S = rev(S) + S,代价为 1;
给定一个目标串 S,要求你通过上述四种操作,用最少的代价合成出目标串。初始只有一个空串。

Solution

观察可以发现三个性质:

  1. 每次合成最终的串的方法一定是先合成一个回文串,然后两边的字符暴力添加。
  2. 一个偶数长度的回文串的合成方法一定是先合成一半的串,然后翻转。
  3. 合成一个偶数长度的回文串的左半边与右半边的步数相同。

考虑在回文树上DP,设\(f(s)\)为在合成回文串\(s\)的最小代价。
同时在回文树求出\(fail_s\)(\(s\)的最长回文前缀(后缀)),\(fa_s\)(\(s\)在回文树上的父亲,\(half_s\)(不超过s长度一半的最长回文前缀)。

  • 如果\(s\)为奇数长度的回文串,则\(f_s=min(f_{fa_s}+2,f_{fail_s}+|s|-|fail_s|\)。因为\(s\)长度为奇数,所以不可能由翻转得出,只可能由首尾加字符得来。
  • 如果\(s\)为偶数唱的回文串,则合成\(s\)的最后一步一定是翻转。而\(s\)的一半却不一定是回文串。所以考虑把转移合并。若翻转前在串首增加了字符,则\(f_s=f_{fa_s}+1\)表示\(s_fa\)在最后一步翻转前在首部增加了字符。若翻转加倍前未在尾部增加了字符则\(f_s=f_{s_{half}}+\frac{s_{len}}{2}\)表示先合成\(s_{half}\)然后在尾部添加字符合成\(s\)的一半。最后翻转加倍。

F.[省队集训2015day1T1]月宫的符卡序列

Description

题意

Solution

这道题我的做法是用Manacher建出一个类似回文树的东西。
对这个串进行Manacher的预处理,使得每个回文串的长度都为奇数。
现在考虑建出这棵回文树(明显,所有回文串都位于odd节点下方)
对于每个位置\(i\),它对每个以它为中心的回文串贡献为\(i\)。设其最远的回文串延伸了\(f_i\),则相当于给串\(s_{[i-f_i+1,i+f_i-1]}\)到根异或上了i。
现在的问题是怎么建出这棵回文树:
在Manacher的算法过程中,设当前中心为i,当前节点为x,如果\(s_{i-f_i}=s_{i+f_i}\),那么\(x'=x→s_{i+f_i}\),这样算法结束,这棵树也就建出来了。
至于每个位置在串中的位置的求法,可以自己yy或者看下代码。

这个是laofu的做法:
先建出回文树并求出\(s_{1..i}\)的最长回文后缀,然后跑Manacher,在Manacher的过程中求出f数组,然后暴跳\(i+f_i\)最长回文后缀的fail,直到len等于f_i为止。

G.[省队集训2017day3T2]回文串

Description

Description

Solution

可以看出题目所求的其实是\(fail\)树的一段路径和。
考虑离线建出最终的回文树,然后在求出每个位置最终的最长回文前缀与后缀。
每次询问实际上的值是\(len_i*right_i\),其中right是字符串的出现次数。用动态树维护即可。
值得注意的是lca有时候不会被统计进答案,所以要特判。

感觉讲的好不清楚啊,不懂来问我吧,QAQ...

完结撒花!
鼓掌熊

感觉回文树很有趣的,大家都来学一下吧。

超人熊

最后声明一下:由于这篇文章包括了部分校内题,所以仅限会员查看。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:回文树总结 by dsl


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!