当前位置:首页 > 字符串 > 正文
GDKOI2021提高组Day1C回文
1153+

题目大意:给定一个长度为n的字符串,m次询问,每次回答区间[l, r]内字符串的最大回文长度。

解题思路

使用Manacher算法预处理出以每个位置为中心的最长回文长度,并用ST表预处理区间回文长度最大值,对于每次询问,二分答案即可。

首先,马拉车算法可以在O(n)得到每个位置(包括空隙)的最长回文长度;

接着,使用倍增得到区间回文中心最大回文长度;

最后,二分答案,长度为m的字符串,在区间[l, r]内,回文中心的范围约l+m>>1~r-m>>1,具体边界可以慢慢考虑。是否有满足要求的答案,就看这里的最大回文长度是否达到m即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,,

GDKOI2021提高组Day1C回文:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!