【bzoj2342】[Shoi2011]双倍回文

2015.06.13 16:54 Sat | 16次阅读 | 旧日oi | 固定链接 | 源码

题目大意

自己看吧……

题解

对于x和x+1之间的对称轴,如果有(x+1,y)可以更新答案,则有p[y]>=y-x(保证了右侧是回文),x+p[x]>=2*y-x(保证了两边都是回文)。然后用manacher求出p[i],这里求的是长度为偶数的,和正常的略有区别。然后按y-p[y]排序,枚举对称轴的位置,把y-p[y]<对称轴的点加进去,每次找x+p[x]/2的前驱节点更新答案就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define N 500005
int n;
char s[N];
int p[N],q[N];
set<int> t;
bool cmp(int a,int b)
{
    return a-p[a]<b-p[b];
}
int main()
{
    cin>>n;
    scanf("%s",s+1);s[0]='#';
    for(int mx=0,id=0,i=1;i<=n;i++)
    {
        if(mx>=i) p[i]=min(mx-i,p[2*id-i]);
        else p[i]=0;
        for(;s[i-p[i]]==s[i+1+p[i]];p[i]++);
        if(i+p[i]>mx) mx=i+p[i],id=i;
        q[i]=i;
    }   
    sort(q+1,q+n+1,cmp);
    int ans=0;
    for(int j=1,i=1;i<=n;i++)
    {
        while(j<=n&&q[j]-p[q[j]]<=i) t.insert(q[j++]);
        set<int>::iterator tmp=t.upper_bound(i+p[i]/2);
        if(tmp!=t.begin()) ans=max(ans,(*--tmp-i)*4);
    }
    cout<<ans<<endl;
}```