BZOJ2342: [Shoi2011]双倍回文

时间:2022-03-29 11:44:28

2342: [Shoi2011]双倍回文

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 923  Solved: 317
[Submit][Status]

Description

BZOJ2342: [Shoi2011]双倍回文

Input

输入分为两行,第一行为一个整数BZOJ2342: [Shoi2011]双倍回文,表示字符串的长度,第二行有BZOJ2342: [Shoi2011]双倍回文个连续的小写的英文字符,表示字符串的内容。

Output

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

Sample Input

16
ggabaabaabaaball

Sample Output

12

HINT

N<=500000

Source

字符串

题解:好逗比的一道题。。。

先manacher一遍,然后比较暴力的思路就是枚举中心点,枚举这个字串的长度,然后判断是否合法并更新答案。

果然会T 11s+

然后加了个最优性剪枝,当当前长度<ans的时候就不枚举了,然后就72ms过了。。。

代码:

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000000+5

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }
int n,p[maxn];
char s[maxn],st[maxn]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();scanf("%s",st+);
for1(i,n)s[i<<]=st[i];n<<=;n++;
for(int i=;i<=n;i+=)s[i]='#';
int id=,mx=;
for(int i=;i<=n;i+=)
{
if(mx>i)p[i]=min(p[*id-i],mx-i);
while(i-p[i]>&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]])p[i]++;
if(i+p[i]>mx)mx=i+p[i],id=i;
}
int ans=;
for(int i=;i<=n;i+=)
{
int j=(p[i]-)>>;
if(j&)j--;
for(;j>&&*j>ans;j-=)
if(p[i-j]->=j&&p[i+j]->=j)ans=max(ans,*j);
}
printf("%d\n",ans); return ; }

UPD:看题解居然看到了并查集,splay。。。orzzzzzz