题解 P4287 【[SHOI2011]双倍回文】

xzyxzy · 2018-06-07 15:22:45 · 题解

~~我竟然是第一个发题解的？！~~

正文

考虑我们用Manacher是怎么求最长回文子串的（如果不会，请戳我）

那么如果是双倍回文字串的话，枚举到右子回文串的中心的时候，对应地找到最长双倍回文子串的中心，然后对称地看是否符合条件

举个例子

#b#a#a#b#b#a#a#b# 当我枚举到第13位的时候（从1开始），将13作为右子串中心，找到双倍回文子串中心第9位，对称看第5位也满足条件，那么更新答案

我们会发现一些规律

左右串中心和全串中心必须要是#
能够被右串中心计算到的全串中心是一段区间（原来我以为是一个点，WA了Test6），可以用队列维护（但是对于全是a的会T，所以加上t-h<100）
答案就是(i-Centre)*2

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=1500000;
int N,l,C,R,p[MAXN],Ans;
int Q[MAXN],h,t;
char s[MAXN];
int main()
{
    cin>>N;
    char ch=getchar();
    while(ch>'z'||ch<'a') ch=getchar();
    s[++l]='#';
    while(ch>='a'&&ch<='z')
    {
        s[++l]=ch;s[++l]='#';
        ch=getchar();
    }
    for(int i=1;i<=l;i++)
    {
        if(i<R)
        {
            p[i]=min(p[C*2-i],R-i);
            while(t-h>100||((i-Q[h])*2>p[Q[h]]&&h<t)) h++;
            for(int j=h;j<=t;j++)
                if(s[i]=='#'&&s[Q[j]]=='#'&&i-Q[j]+1<=p[i])
                    Ans=max(Ans,(i-Q[j])*2);
        }
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]&&i-p[i]>=1&&i+p[i]<=l) p[i]++;
        if(i+p[i]>R) R=i+p[i],C=i,Q[++t]=i;
    }
    printf("%d\n",Ans);
    return 0;
}

刚才卡了一卡，发现能够转移的取6个就可以了，也就是t-h<6

~~作为最短又最快的代码，我有点飘啊。。~~

题解 P4287 【[SHOI2011]双倍回文】

广告

正文