首页 > 试题广场 >

Manacher算法进阶问题

[编程题]Manacher算法进阶问题
  • 热度指数：588 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添加的最短字符串
[举例]
str = "abcd123321"，在必须包含最后一个字符的情况下，最长的回文子串是"123321"，之前不是最长回文子串的部分是'abcd"，所以末尾应该添加的部分就是"dcba"。
[要求]
如果str的长度为N，解决进阶问题的时间复杂度为O(N).
保证输入数据无回文串

输入描述:
输入为一个字符串str


输出描述:
输出一个字符串。
示例1

输入

abcd123321

输出

dcba

说明

添加后的字符串为abcd123321dcba
示例2

输入

ababab

输出

a

备注:
设N表示输入字符串的长度
保证输入字符中只含有小写字母及数字
算法知识视频讲解
开通博客

暂无题解

问题信息

字符串
上传者：小小
难度：
4条回答 2319浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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