【SHOI2011】bzoj2342 双倍回文

本文主要是介绍【SHOI2011】bzoj2342 双倍回文，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

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

Output

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

首先由题意可知，只用考虑偶数长的回文串。这样就不用插入#，直接manacher即可。
其中p[i]表示以i和i+1的中点为对称轴，最大回文串长度的一半。
接下来考虑求解，设答案表示为i..j,k..x,x+1..y,y+1..q，这四段分别为w,wr,w,wr。只考虑x和y，则合法的条件为y-p[y]<=x【后两段是回文串】且y<=x+p[x]/2【整个是回文串】。
具体做法是先将y按y-p[y]排序，然后扫描x，把满足y-p[y]<=x的y插入set中，在查找最大的小于等于x+p[x]/2的y更新答案。
整体复杂度O(nlogn)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int l,p[500010],a[500010];
char s[500010];
set<int> se;
set<int>::iterator it;
bool cmp(const int &a,const int &b)
{return a-p[a]<b-p[b];
}
void mana()
{int i,j,k,id,mx=0;s[0]='@';s[l+1]='$';for (i=1;i<=l;i++){if (i<mx) p[i]=min(p[2*id-i],mx-i);else p[i]=0;while (s[i-p[i]]==s[i+p[i]+1]) p[i]++;if (i+p[i]>mx){mx=i+p[i];id=i;}}
}
void solve()
{int i,j,k,x,y,z,now=0,ans=0;for (i=1;i<=l;i++)a[i]=i;sort(a+1,a+l+1,cmp);se.insert(-1);se.insert(-2);for (i=1;i<=l;i++){while (now<l&&a[now+1]-p[a[now+1]]<=i){now++;se.insert(a[now]);}x=*(--se.upper_bound(i+p[i]/2));if (x<0) continue;ans=max(ans,4*(x-i));}printf("%d\n",ans);
}
int main()
{scanf("%d%s",&l,s+1);mana();solve();
}