点击打开链接 推荐文章

符合正常可接受复杂度的话，就用Manacher来判断回文的性质吧。

代码如下：

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std ;
#define MAX 1000
char s[MAX];
char new_s[MAX];
int p[MAX];
int rem ;
int init(){
    int Count = 0 ;
    new_s[Count++]='$';
    new_s[Count++]='#';
    for(int i = 0 ; i < strlen(s) ; i ++ )
    {
        new_s[Count++] = s[i];
        new_s[Count++] = '#';
    }
    new_s[Count] = '#';
    return Count ;
}

int Manacher()
{
    int len = init();
    int mx = 0 ;
    int id = 0 ;
    int max_len= 0 ;
    for(int i = 1 ; i < len ; i ++ )
    {
        if(i<mx)
        {
            p[i]=min( p[2*id-i],mx-i);
        }else {
            p[i]= 1 ;
        }
        while(new_s[i+p[i]]==new_s[i-p[i]])
        {
            p[i] ++ ;
        }
        if(mx< i +p[i])
        {
            id = i ;
            mx = i+p[i];

        }
        if(max_len < p[i]-1)
        {
              rem = i;
              max_len = p[i]-1;
        }

    }
    return max_len ;
}

int main(){
    while(~scanf("%s",s))
    {
        int max_len = Manacher();

        for(int i = rem-max_len ; i <=rem+max_len ; i ++)
        {
             if(new_s[i]!='#')
                cout << new_s[i];
        }
        cout <<endl;
    }
}