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

HINT

N<=500000

Source

字符串

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

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

果然会T 11s+

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

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 1000000+5
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 int n,p[maxn];
61 char s[maxn],st[maxn];
62 
63 int main()
64 
65 {
66 
67     freopen("input.txt","r",stdin);
68 
69     freopen("output.txt","w",stdout);
70 
71     n=read();scanf("%s",st+1);
72     for1(i,n)s[i<<1]=st[i];n<<=1;n++;
73     for(int i=1;i<=n;i+=2)s[i]='#';
74     int id=0,mx=0;
75     for(int i=1;i<=n;i+=2)
76     {
77         if(mx>i)p[i]=min(p[2*id-i],mx-i);
78         while(i-p[i]>0&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]])p[i]++;
79         if(i+p[i]>mx)mx=i+p[i],id=i;
80     }
81     int ans=0;
82     for(int i=1;i<=n;i+=2)
83     {
84         int j=(p[i]-1)>>1;
85         if(j&1)j--;
86         for(;j>0&&2*j>ans;j-=2)
87          if(p[i-j]-1>=j&&p[i+j]-1>=j)ans=max(ans,2*j);
88     }
89     printf("%d
",ans);
90 
91     return 0;
92 
93 }

View Code

UPD：看题解居然看到了并查集，splay。。。orzzzzzz