题目

 

 

分析

（sb如我写了发不知道什么东西在洛谷上竟然水了84分

嗯咳

设$ i $为双重回文的中心

如果$ j~i $ 可以被算作答案，只有满足如下两式：

• $ p[j]+j \geq i $
• $ 2*(i-j) \leq p[j] $

计算时我们先做一次马拉车，然后按照 $ p[j]+j \geq i $排序，保证它的单调，接着把满足$ 2*(i-j) \leq p[j] $扔进set里询问。

 

代码

#include 
      
       using namespace std;const int maxn=1050000;char s2[maxn],s[ maxn];int p[ maxn], len;set
       
         t;void Manacher(){    len=strlen(s2+1);    for(int i=1;i<=len;i++){        s[i*2-1]='#'; s[i*2]=s2[i];    }     s[len=len*2+1]='#';      int right=0, pos=0;     for(int i=1;i<=len;i++){         if(i
        
         0 && s[i+p[i]]==s[i-p[i]]) p[i]++;        if(i+p[i]>right){            right=i+p[i]; pos=i;        }     }}int q[maxn], f[maxn];bool cmp(int a,int b){ return (a-f[a])<(b-f[b]); }int main(){    int n;    scanf("%d%s",&n,s2+1);     Manacher();    for(int i=1;i<=n;i++) q[i]=i, f[i]=(p[i*2+1]-1)/2;    sort(q+1,q+1+n,cmp);    int now=1,ans=0;    for(int i=1;i<=n;i++){        while(now<=n&&q[now]-f[q[now]]<=i) {            t.insert(q[now]);            now++;        }        set
         
          ::iterator tmp=t.upper_bound(i+f[i]/2);        if(tmp!=t.begin ()){            ans=max(ans,(*--tmp - i));        }    }    printf("%d\n",ans*4);    return 0;}/*17qwertyuaabbaabbaa*/