首页 > 试题广场 > Manacher算法进阶问题
[编程题]Manacher算法进阶问题
  • 热度指数:202 时间限制: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表示输入字符串的长度
保证输入字符中只含有小写字母及数字
#include<cstdio>
(802)#include<cstring>
bool ishuiwen(char str[],int l,int r){
    int k=0;
    for(int i=l;i<=(l+r)/2;++i){
        if(str[i]!=str[r-k])
            return false;
        ++k;
    }
    return true;
}
int main(){
    char str[500010];
    while(scanf("%s",str)!=EOF){
        int len=strlen(str);
        int i;
        for(i=0;i<len;++i){
            if(ishuiwen(str,i,len-1))
                break;
        }
        for(i=i-1;i>=0;--i){
        	printf("%c",str[i]);
        }
    }
    return 0;
}

发表于 2020-03-25 15:43:32 回复(0)