BZOJ 2342 [Shoi2011] 双倍回文


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2342

题意:定义串 q 的倒置为 p,则串 q 的双倍回文串为形如 qpqp 的串。求给定串里的最长双倍回文串。


发现一个双倍回文串是由两个回文串组成的,这个串恰好为双倍回文串的一个长度为一半的后缀。

这个串在 PAM 的 fail 树上一定为那个回文串的祖先,由于长度是一半,只会有最多一个节点满足这个限制。

所以直接用一个桶存各种串长的出现情况即可,优雅的一逼。 就是跑的不太快。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2342 [Shoi2011] 双倍回文


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,