bzoj2565: 最长双回文串

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;
}

  

上一篇:VB将MSHFlexGrid数据导出到Excel文件通用功能


下一篇:UIAlertController弹出提示框