首页 > 试题广场 >

小A的回文串

[编程题]小A的回文串
  • 热度指数：488 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小A非常喜欢回文串，当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少，但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动，他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。

输入描述:


输出描述:
一行输出一个整数，表示通过这样的操作后可以得到最大回文子串的长度。
示例1

输入

dcbaabc

输出

7

说明

将前面的dcba移动到末尾变成abcdcba，这个字符串的最大回文子串就是它本身，长度为7

备注:
算法知识视频讲解
开通博客
头像 瑜画
发表于 2020-06-11 14:00:54
将字符串变成原来的两倍，即s=s+s，然后枚举长度小于等于n的子串，对子串进行马拉车算法，不断更新ans的值。 #include <bits/stdc++.h> using namespace std; string s; string str; int p[10050]; void g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 nagisa_菜鸡
发表于 2020-08-03 23:24:52
回文串大家都很熟悉，但我们平常使用的方法是枚举中心点向外扩展求，复杂度是.但这道题，需要枚举n种字符串，每个最长为5e3，若找最大长度会炸，所以，需要马拉车算法优化，复杂度为。具体算法内容网上有很多。具体看代码注释吧。 #include <iostream> #include <m 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

枚举
难度：
0条回答 12浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小A的回文串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号