BZOJ2342: [Shoi2011]双倍回文

2342: [Shoi2011]双倍回文

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

Description

Input

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

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