题意：

给定字符串。求字符串中的最长回文序列

解题思路：

manacher 算法

时间复杂度：O(N)

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAXN 110010

using namespace std;

char b[MAXN],a[MAXN<<1];

int p[MAXN<<1];

int n;

int main(){

    while(scanf("%s",&b[1])!=EOF){

        int i;

        for(i=1;b[i]!='\0';++i){

            a[(i<<1)]=b[i];

            a[(i<<1)+1]='#';

        }

        a[0]='?';

        a[1]='#';

        n=(i<<1)+2;

        a[n]=0;

        int MaxId,MaxL,id;

        MaxId=MaxL=0;

        memset(p,0,sizeof(p));

        for(int i=1;i<n;++i){

            if(MaxId>i)

                p[i]=min(p[2*id-i],MaxId-i);

            else

                p[i]=1;

            while(a[i+p[i]]==a[i-p[i]])

                p[i]++;

            if(p[i]+i>MaxId)

            {

                MaxId=p[i]+i;

                id=i;

            }

            if(p[i]>MaxL)

                MaxL=p[i];

        }

        printf("%d\n",MaxL-1);

    }

    return 0;

}