【BZOJ-2342】双倍回文 Manacher + 并查集

2342: [Shoi2011]双倍回文

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1799  Solved: 671
[Submit][Status][Discuss]

Description

【BZOJ-2342】双倍回文      Manacher + 并查集

Input

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

Output

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

Sample Input

16
ggabaabaabaaball

Sample Output

12

HINT

N<=500000

Source

Solution

看完题大体的思路就是先一遍Manacher,O(n)求出回文串,然后进行判断

题目中说的很清楚,双倍回文串长度一定是4的倍数,即为偶数,那么Manacher出来的回文串中心一定在字符间添加的'#'上

那么考虑要求的东西 y+p[y]>=x && y>=x-p[x]/2,思考一个枚举的方法

枚举j,如果j不能覆盖到当前的i,那么一定是不符合覆盖到i+1的,所以,之后的所有事和它无关,可以忽略,这样想,维护一下就好了,采取并查集

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 500010
char S[maxn],s[maxn<<];
int n,len,mx,id,p[maxn<<],fa[maxn<<],ans;
void PreWork()
{
memset(p,,sizeof(p));
len=n<<|;
for (int i=; i<=n; i++)
s[i<<]=S[i],s[i<<|]='#';
s[]='$'; s[]='#'; s[len+]='%';
}
void Manacher()
{
PreWork();
for (int i=; i<=len; i++)
{
if (mx>i) p[i]=min(p[id*-i],mx-i);
else p[i]=;
while (s[i-p[i]]==s[i+p[i]]) p[i]++;
if (p[i]+i>mx) mx=p[i]+i,id=i;
}
}
int find(int x) {if (fa[x]==x) return x; else return fa[x]=find(fa[x]);}
int main()
{
scanf("%d",&n); scanf("%s",S+);
Manacher();
for (int i=; i<=len; i++)
if (s[i]=='#') fa[i]=i; else fa[i]=i+;
for (int i=; i<=len-; i+=)
{
int f=find(max(i-p[i]/,));
while (f<i && f+p[f]<i) fa[f]=find(f+),f=fa[f];
if (f<i && (i-f)*>ans) ans=(i-f)*;
}
printf("%d\n",ans);
return ;
}
上一篇:spring加载过程,源码带你理解从初始化到bean注入


下一篇:C语言 · 确定元音字母位置