「BZOJ2342」[SHOI2011] 双倍回文

2014年12月3日6,6350

Description

Input

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

Output

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

Sample Input

16
ggabaabaabaaball

Sample Output

HINT

N<=500000

题解

p[i]表示i和i+1为中心的最长回文子串长度/2（str[i-k]=str[i+1+k]）。。。

用manacher On计算p数组

题目要求计算w wR w wR的最大长度

枚举x为对称轴。。。实际上对称轴在x到x+1之间，即x是第一个wR的最后一位

举些例子推一推发现len(x+1,y)*4能更新答案，仅当y-p[y]<=x且y<=x+p[x]/2

按照y-p[y]排序一下，递推x的时候将符合1式的y插入set，在set中查找x+p[x]/2的前驱更新答案即可

复杂度On+nlogn

usedtobe提出如果把题目要求改成w wR w。。。这样的话限制应该是y<=x+p[x]且y-p[y]<=x

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,ans;
char ch[500005];
int p[500005],q[500005];
set<int> t;
void manacher()
{
	int mx=0,id;
	for(int i=1;i<=n;i++)
	{
		if(mx>=i)p[i]=min(mx-i,p[2*id-i]);
		else 
			p[i]=0;
		for(;ch[i+p[i]+1]==ch[i-p[i]];p[i]++);
		if(p[i]+i>mx)id=i,mx=p[i]+i;
	}
}
bool cmp(int a,int b)
{
	return (a-p[a])<(b-p[b]);
}
int main()
{
	n=read();
	scanf("%s",ch+1);
	ch[0]='#';
	manacher();
    for(int i=1;i<=n;i++)q[i]=i;
	sort(q+1,q+n+1,cmp);
	int now=1;
	for(int i=1;i<=n;i++)
	{
		while(now<=n&&q[now]-p[q[now]]<=i)
		{
			t.insert(q[now]);
			now++;
		}
		set<int>::iterator tmp=t.upper_bound(i+p[i]/2);
		if(tmp!=t.begin())
		{
			ans=max(ans,(*--tmp-i)*4);
		}
	}
	printf("%d\n",ans);
	return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000007

#define inf 1000000000

using namespace std;

int read()

{

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

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

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

return x*f;

}

int n,ans;

char ch[500005];

int p[500005],q[500005];

set<int> t;

void manacher()

{

int mx=0,id;

for(int i=1;i<=n;i++)

{

if(mx>=i)p[i]=min(mx-i,p[2*id-i]);

else

p[i]=0;

for(;ch[i+p[i]+1]==ch[i-p[i]];p[i]++);

if(p[i]+i>mx)id=i,mx=p[i]+i;

}

bool cmp(int a,int b)

{

return (a-p[a])<(b-p[b]);

}

int main()

{

n=read();

scanf("%s",ch+1);

ch[0]='#';

manacher();

for(int i=1;i<=n;i++)q[i]=i;

sort(q+1,q+n+1,cmp);

int now=1;

for(int i=1;i<=n;i++)

{

while(now<=n&&q[now]-p[q[now]]<=i)

{

t.insert(q[now]);

now++;

}

set<int>::iterator tmp=t.upper_bound(i+p[i]/2);

if(tmp!=t.begin())

{

ans=max(ans,(*--tmp-i)*4);

}

printf("%d\n",ans);

return 0;

}

「BZOJ3790」神奇项链 »

分类目录

计数器 9850657
OI 课件=>

hzwer.com _ Home | http://hzwer.com