BZOJ2565：最长双回文串——题解

时间：2022-02-18 09:19:10

http://www.lydsy.com/JudgeOnline/problem.php?id=2565

题目大意：

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
 
——————————————————————
看到回文串长度最大，先敲一个manacher算法。
然后思考如何更新每一个字符以其为起点和终点的最长回文串。
显然都跑一遍肯定是不行的（尝试过TLE…）
那么我们考虑一个很简单的事实，对于一个在某几个回文串的字符，显然当它属于mx靠前的回文串时以它为终点的回文串长度最长。
那么我们就有了一种近似O(n)的算法，通过记录我们最新一次更新的字符位置now，然后搜索每一个回文串，当回文串右端点超过了now的时候，就对now和右端点之间的字符更新。
同理处理另一种情况，然后枚举取最大值即可。
 
PS：我们已知回文串的中点i，怎么求在回文串内的j以其为终点的回文串长度。
我们有结论为j-i+1，简易证明：
我们知道我们最开始的时候是含有“#”插入的字符串处理，此时回文串的长度为2*(j-i)+1.
而实际上其中包含了“#”有j-i个（就是长度/2向下取整）。
相减得到j-i+1。
 
#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 100010

using namespace std;

int left[*N],right[*N],mx,id,p[*N];

char s[*N];

int main(){

    scanf("%s",s+);

    int l=strlen(s+);

    s[]='@';

    for(int i=l;i>=;i--)s[i*]=s[i];

    for(int i=;i<=*l+;i+=)s[i]='#';

    s[*l+]='?';

    l=*l+;

    for(int i=;i<=l;i++){

    if(mx>i)p[i]=min(p[*id-i],mx-i);

    else p[i]=;

    while(s[i-p[i]]==s[i+p[i]])p[i]++;

    if(i+p[i]>mx){

        mx=i+p[i];

        id=i;

    }

    }

    int now=;

    for(int i=;i<=l;i++){

    if(i+p[i]->now){

        for(int j=now+;j<=i+p[i];j++){

        left[j]=j-i+;

        }

        now=i+p[i]-;

    }

    }

    now=l+;

    for(int i=l;i>=;i--){

    if(i-p[i]+<now){

        for(int j=now-;j>=i-p[i];j--){

        right[j]=i-j+;

        }

        now=i-p[i]+;

    }

    }

    int ans=;

    for(int i=;i<=l;i+=){

    ans=max(ans,left[i]+right[i+]);

    }

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

    return ;

}

相关文章