BZOJ2565: 最长双回文串（Manacher）

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

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

Output

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

Sample Input

baacaabbacabb

Sample Output

解题思路：

是求两个回文串相加的双回文最大长度。

一直在想两个回文串相交的情况，结果发现是不存在的，那样只会形成更大的一个回文串，蒟蒻就是蒟蒻

记录最右点和最左点。

注意更新！！

代码:

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using std::min;

 using std::max;

 char a[];

 int l[];

 int ls[];

 int rs[];

 int f[];

 int ans;

 int cnt;

 int main()

 {

     scanf("%s",a+);

     int len=strlen(a+);

     l[cnt]='&';

     for(int i=;i<=len;i++)

     {

         l[++cnt]='&';

         l[++cnt]=a[i];

     }

     l[++cnt]='&';

     int mx=;

     f[]=;

     for(int i=;i<=cnt;i++)

     {

         f[i]=min(f[mx*-i],f[mx]+mx-i);

         while(f[i]+i<=cnt&&l[f[i]+i]==l[i-f[i]])

             f[i]++;

         if(mx+f[mx]<i+f[i])

             mx=i;

         rs[f[i]+i-]=max(rs[f[i]+i-],f[i]-);

         ls[i-f[i]+]=max(ls[i-f[i]+],f[i]-);

     }

     for(int i=;i<=cnt;i+=)

         ls[i]=max(ls[i],ls[i-]-);

     for(int i=cnt;i>=;i-=)

         rs[i]=max(rs[i],rs[i+]-);

     for(int i=;i<=cnt;i+=)

         ans=max(ans,rs[i]+ls[i]);

     printf("%d\n",ans);

     return ;

 }

秒客网