Manacher+回文自动机 专题训练

发布于 2018-01-16  6.06k 次阅读


本来计划着刷完网络流马上去博弈论的,可是做了两道题之后发现有点做不动了,就先花了半天来复习字符串,顺便把之前的坑都填上。

BZOJ2342 [Shoi2011]双倍回文

这道题用回文自动机应该是比较简单。因为满足要求的1/2回文串节点一定在当前节点的fail指针指向的祖先中,所以只需要建出回文自动机,然后跑DFS,开个桶记录一下就好了。

 

BZOJ2565 最长双回文串

首先有个结论,就是最长双回文串一定是由两个最长回文串尽量长地拼接起来的(也就是说,双回文串的断点使得左侧或右侧的串不能再拓展)。

那么知道了这个结论,就可以PAM直接搞了。

 

BZOJ2084 [Poi2010]Antisymmetry

考虑这样的串有什么性质,发现这样的串对称位置的字符一定互不相同,而且,为了满足互不相同的条件,串长必须是偶数,否则无法保证对称轴处的字符不同。

如果直接跑manacher,那么边界好像非常不好处理,于是可以考虑利用偶回文串性质,直接改一下manacher的板子,不加特殊字符,只计算偶回文串即可。具体实现就是枚举对称轴的位置,更新也都是基于对称轴(两个字符的缝隙)搞得。

 

BZOJ3160 万径人踪灭

比较综合,FFT+manacher(要是用PAM计算回文串也无所谓)。首先,题意就是要求统计既满足位置对称,又满足回文且整个序列不连续的01子序列个数。先不考虑不连续的性质,因为字符集只有01,所以可以跑两遍FFT来计算满足位置对称且回文的序列数。比如,a的式子长这样。

$$C_i=\sum_{j+k=i}[A_{j}=='a']*[B_{k}=='a']$$

那么,C[i]对答案的贡献就是(2^(C[i]/2))-1(显然),注意除法是向上取整。

最后,用manacher计算回文子串的个数,用之前的结果减一下即可。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974