首页 > ABB
开通博客写题解
头像 __故人__
发表于 2020-10-03 17:41:13
分析 我们需要加几个字符在末尾将其变为回文串。那么我们可以很容易考虑到，回文中心一定在这个字符串上。那么当一个回文中心确定时，这个串其实也就确定了。那么添加的长度为 。所以我们就应该寻找最大的可行的 。那么当一个字符可以为回文中心时当且仅当，回文中心加上回文半径覆盖了第 个字符的。那么求出每个 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 阿哲不是吧
发表于 2020-10-01 15:14:49
ABB 题意： 长度为n的字符串，问最少添加多少字符可以使其构成回文字符串 题解： 最长回文字符串我的第一反应是manacher马拉车算法，那我们直接马拉车找到已有最长回文串，然后总长度减去不就是答案吗？非也 ~ ~ 。注意是让我们构造最长回文字符串，我们会发现，如果我们用马拉车找到的最长回文串的最 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”