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

HINT

样例说明

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

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

Solution

在manacher的时候顺便统计一下以每个位置为结束/开始的最长回文串最后枚举统计答案就好了

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (200000+1000)

 using namespace std;

 int n,tot,len[N],ans,E[N],S[N];

 char s[N],a[N];

 void Manacher()

 {

     int x,mid=,maxn=;

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

     {

         if (i>maxn) x=;

         else x=min(maxn-i+,len[mid*-i]);

         S[i-x+]=max(S[i-x+],x*-);

         E[i+x-]=max(E[i+x-],x*-);//这里一开始忘加了

         while (s[i+x]==s[i-x])

         {

             ++x;

             S[i-x+]=max(S[i-x+],x*-);

             E[i+x-]=max(E[i+x-],x*-);

         }

         len[i]=x;

         if (i+x->maxn) maxn=i+x-,mid=i;

     }

 }

 int main()

 {

     scanf("%s",a);

     n=strlen(a);

     s[++tot]='@'; s[++tot]='#';

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

         s[++tot]=a[i], s[++tot]='#';

     s[++tot]='$';

     Manacher();

     for (int i=; i<tot-; i+=)

         ans=max(ans,(S[i]+E[i]-)/);

     printf("%d",ans);

 }

秒客网