BZOJ2565: 最长双回文串

【传送门：BZOJ2565】

简要题意：

　　给出一个串，求出一个最长的子串，满足能够分成两个回文串

题解：

　　这题，果断马拉车！！（Manacher）

　　首先对原串进行Manacher，然后同时记录两个数组：llen，rlen

　　llen[i]表示以第i位为开头的最长回文串的长度，rlen[i]表示以第i位为结尾的最长回文串的长度

　　这两个数组怎么得到呢？

　　假设当前对i点进行操作，那么p[i]假设已经求出来了，那么：

　　rlen[i-p[i]+1]=max(rlen[i-p[i]+1],p[i]-1)

　　llen[i+p[i]-1]=max(llen[i+p[i]-1],p[i]-1)

　　注意：因为我们在求Manacher的时候会将原字符串进行修改，然后得出来的p[i]-1之后才是原字符串的最长回文子串长度，所以我们llen和rlen记录的都是原长度

　　但是仅仅这样还不能求出准确的rlen,llen

　　我们还要将这两个数组往前往后问一下，假如之前得到的最长回文串长度-1比当前数组的值还大的话，也要更新

　　具体，代码解释

参考代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char st[110000],now[210000];
int p[210000];
int llen[210000],rlen[210000];
int len;
void Manacher()
{
    for(int i=1;i<=len;i++) now[2*i-1]='#',now[2*i]=st[i];
    now[2*len+1]='#';
    len=2*len+1;
    int pos=0,R=0;
    for(int i=1;i<=len;i++)
    {
        int j=2*pos-i;
        if(i<=R) p[i]=min(p[j],R-i);
        else p[i]=1;
        while(1<=i-p[i]&&i+p[i]<=len&&now[i-p[i]]==now[i+p[i]]) p[i]++;
        if(i+p[i]-1>R){pos=i;R=i+p[i]-1;}
    }
    for(int i=1;i<=len;i++)
    {
        rlen[i-p[i]+1]=max(rlen[i-p[i]+1],p[i]-1);
        llen[i+p[i]-1]=max(llen[i+p[i]-1],p[i]-1);
    }
    for(int i=2;i<=len;i++) rlen[i]=max(rlen[i-1]-1,rlen[i]);
    for(int i=len-1;i>=1;i--) llen[i]=max(llen[i+1]-1,llen[i]);
}
int main()
{
    scanf("%s",st+1);
    len=strlen(st+1);
    Manacher();
    int ans=0;
    for(int i=1;i<=len;i++) ans=max(ans,rlen[i]+llen[i]);
    printf("%d
",ans);
    return 0;
}