A1280. 最长双回文串

时间限制：

2.0s   内存限制：512.0MB  

总提交次数：   AC次数：   平均分：

 

将本题分享到：

      

   

       

试题来源

　　中国国家队清华集训 2011-2012 第二天

问题描述

　　顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。

　　输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

输入格式

　　一行由小写英文字母组成的字符串S。

输出格式

　　一行一个整数，表示最长双回文子串的长度。

样例输入

baacaabbacabb

样例输出

12

样例说明

　　从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

数据规模及限制

　　对于10%的数据，2≤|S|≤10

³。

　　对于30%的数据，2≤|S|≤10

⁴。

　　对于100%的数据，2≤|S|≤10

⁵。

　　时间限制：2秒

/*    一开始只写了从左到右贪心选取，在青橙上A了，bzoj上wa了    然后又改成了正着一遍，反着一遍，就过了*/#include
      
       #include
       
        #include
        
         #define maxn 100010using namespace std;char s[maxn];int nxt[maxn][30],fail[maxn],len[maxn],str[maxn],sz=-1,last,n,a[maxn];int creat(int l){    len[++sz]=l;return sz;}void prepare(){    last=n=0;sz=-1;    memset(fail,0,sizeof(fail));    memset(nxt,0,sizeof(nxt));    creat(0);    creat(-1);    str[0]=-1;    last=0;    fail[0]=1;}int getfail(int x){    while(str[n-len[x]-1]!=str[n])x=fail[x];    return x;}void Insert(int c,int id){    str[++n]=c;    int cur=getfail(last),now;    if(!nxt[cur][c]){        now=creat(len[cur]+2);        fail[now]=nxt[getfail(fail[cur])][c];        nxt[cur][c]=now;    }    last=nxt[cur][c];    a[id]=last;}int main(){    prepare();    scanf("%s",s);    int l=strlen(s);    for(int i=0;i
         
          =0;i--)        Insert(s[i]-'a'+1,i);    for(int i=0;i