首页 > 其他 > 详细

bzoj2565: 最长双回文串

时间:2016-01-16 20:53:54      阅读:145      评论:0      收藏:0      [点我收藏+]

manacher之后乱搞

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define N 200005
#define to(x) ((x)+p[x])
#define from(x) ((x)-p[x])

using namespace std;
char s[N];
int n;
int p[N];
bool cmp(int a,int b){
	return from(a)<from(b);
}
int a[N];


int main(){
	scanf("%s",s+1);n=strlen(s+1)*2+1;
	for (int i=n;i;--i) s[i]=(i&1)?‘*‘:s[i>>1];
	int M=0;p[0]=0;s[0]=‘@‘;s[n+1]=‘#‘;
	for (int i=1;i<=n;(M=to(i)>to(M)?i:M),i++)
		for (p[i]=(M+p[M]>i)*min(M+p[M]-i,p[2*M-i]);s[i+p[i]+1]==s[i-p[i]-1];++p[i]);
	int ans=0,j=0;
	for (int i=1;i<=n;++i) a[i]=i;
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;++i){
		while (to(j)<from(a[i])) ++j;
		ans=max(ans,to(a[i])-j*2+from(a[i]));
	}
	printf("%d\n",ans/2);
	return 0;
}

  

bzoj2565: 最长双回文串

原文:http://www.cnblogs.com/wangyurzee7/p/5136284.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!