2342: [Shoi2011]双倍回文
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 923 Solved: 317
[Submit][Status]
Description
Input
输入分为两行,第一行为一个整数,表示字符串的长度,第二行有个连续的小写的英文字符,表示字符串的内容。
Output
输出文件只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。
Sample Input
16
ggabaabaabaaball
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