BZOJ——2565最长双回文串

题目链接->传送门

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

思路：马拉车填充后求出每个字符的回文半径，在枚举所有的#，找以此#为中心最左和最右的回文串长度，这里分别用l[i]和r[i]表示，i是小回文串的中心，双回文串长度恰好等于l[i]+r[i]。

贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#define N 100005
using namespace std;
int p[N<<1],l[N<<1],r[N<<1];
char s[N],t[N<<1];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    int i;
    for(i=1; i<=len; i++)
        t[2*i]=s[i-1],t[2*i+1]='#';
    t[0]='!',t[1]='#';
    t[2*len+2]='\0';
    len=2*len+1;
    int mx=0,id=0,ans=0;
    for(i=1; i<=len; i++)
    {
        if(mx>i) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while(t[i+p[i]]==t[i-p[i]]) p[i]++;
        if(mx<i+p[i]) mx=i+p[i],id=i;
    }
    i=1;
    for(id=3; id<=len-2; id+=2)//#为分割点枚举
    {
        for(; i<=len; i++)//i不用从头开始循环，否则超时
        {
            if(i+p[i]-1>=id)//小回文串回文半径大于枚举中心才行
            {
                l[id]=i;//以id为结尾的最左边字符串中心为i
                break;//跳出，分割点右移，因为如果再让i增加就不是最左的回文串了
            }
        }
    }
    i=len;
    for(id=len-2; id>=3; id-=2)
    {
        for(; i>=1; i--)
        {
            if(i-(p[i]-1)<=id)
            {
                r[id]=i;
                break;
            }
        }
    }
    for(id=3; id<=len-2; id++)
        ans=max(ans,r[id]-l[id]);
    printf("%d\n",ans);
    return 0;
}

秒客网