当前位置: 代码迷 >> 综合 >> BZOJ2342 [Shoi2011]双倍回文 【manacher】
  详细解决方案

BZOJ2342 [Shoi2011]双倍回文 【manacher】

热度:88   发布时间:2023-12-25 04:44:52.0

题目

这里写图片描述

输入格式

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

输出格式

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

输入样例

16

ggabaabaabaaball

输出样例

12

提示

N<=500000

题解

manacher找出所有回文串
枚举总的中心,再向左枚举次中心
似乎不会T。。还跑得挺快

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 1000005,maxm = 100005,INF = 1000000000;
char T[maxn],s[maxn];
int len,n,RL[maxn];
void manacher(){int pos = 0,MR = 0;for (int i = 1; i <= n; i++){if (MR > i) RL[i] = min(RL[2 * pos - i],MR - i);else RL[i] = 1;while (s[i + RL[i]] == s[i - RL[i]]) RL[i]++;if (i + RL[i] > MR) MR = i + RL[i],pos = i;}
}
int main(){scanf("%d\n",&len); gets(T + 1); s[0] = '*';REP(i,len) s[++n] = '#',s[++n] = T[i];manacher();int ans = 0;for (int i = 1; i <= n; i += 2){int l = (i - RL[i] + 1 + i) >> 1; if (l % 2 == 0) l++;while (l <= i && l + RL[l] < i) l += 2;ans = max(ans,((i - l) / 2) * 4);}printf("%d\n",ans);return 0;
}