[SHOI2011]双倍回文

Description

Input

输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。

Output

输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。

Sample Input

16
ggabaabaabaaball

Sample Output

HINT

N<=500000

首先manacher求出len数组

我们发现一个一个以i为中心的回文串[l,r]是双倍回文

[i,r]也是一个回文串，设这个串的中心为j

求出len数组后，可以写出条件：

$j<=i+\frac{len_i}{2}$

$i>=j-len_j$

我们发现从小到大枚举$i$(也可以从大到小枚举j，换一种枚举方式)

这样一个满足$i>=j-len_j$的$j$同样满足$i+x>=j-len_j$

用一个STL的set，维护j，每次找到小于$i+\frac{len_i}{2}$的最大j

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<set>

 using namespace std;

 struct Node

 {

   int x,id;

 }a[];

 set<int>S;

 int n,loc,mx,len[],po,b[],ans;

 char ch[],s[];

 bool cmp(Node a,Node b)

 {

   return a.id-a.x<b.id-b.x;

 }

 int main()

 {int i,j;

   cin>>n;

   scanf("%s",ch+);

   for (i=;i<=n;i++)

     {

       s[++loc]='#';

       s[++loc]=ch[i];

     }

   s[++loc]='#';s[++loc]='?';

   for (i=;i<=loc;i++)

     {

       if (mx>i)

     len[i]=min(mx-i,len[*po-i]);

       else len[i]=;

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

       if (i+len[i]>mx)

     {

       mx=i+len[i];

       po=i;

     }

     }

   for (i=;i<=n;i++)

     a[i].x=(len[i*+]-)/,a[i].id=i,b[i]=a[i].x;

   sort(a+,a+n+,cmp);

   loc=;ans=;

   for (i=;i<=n;i++)

     {

       while (loc<=n&&a[loc].id-a[loc].x<=i)

     S.insert(a[loc].id),loc++;

       set<int>::iterator it;

       it=S.upper_bound(i+b[i]/);

       if (it==S.begin()) continue;

       ans=max(ans,*(--it)-i);

     }

   cout<<ans*;

 }

秒客网