YZOJ P3906 最长双回文串
时间限制：1000MS 内存限制：131072KB
难度：\(4.0\)
-
题目描述
输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(\left|X\right|, \left|Y\right| \geq 1\)），且 \(X, Y\) 都是回文串。
-
输入格式
一行由小写英文字母组成的字符串 \(S\)。
-
输出格式
一行一个整数，表示最长双回文子串的长度。
-
样例输入
|
1 |
baacaabbacabb |
-
样例输出
|
1 |
12 |
-
样例说明
从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。
-
数据规模与约定
对于 \(100\%\) 的数据， \(2 \leq \left|S\right| \leq 10^5\)。
Source: BZOJ 2565
Manacher 裸题。
正反两遍 Manacher 求出以某个节点为中心向左向右最大能扩展的数量，并枚举分隔符判断即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) char os[105050],s[205050]; int rad[205050],lbeg[205050],rend[205050]; inline void ManacherR(char s[],register int ls) { register int pos=0,mxr=0; for(register int i=1;i<=ls;i++) { if(i < mxr) rad[i]=_min(rad[(pos<<1)-i],mxr-i); else rad[i]=1; while(s[i-rad[i]] == s[i+rad[i]]) rad[i]++; if(mxr < i+rad[i]) { for(register int j=mxr+1;j<=i+rad[i];j++) rend[j]=i; mxr=i+rad[i],pos=i; } } pos=ls+1,mxr=ls+1; // mxr <-> mnl for(register int i=ls;i>=1;i--) { if(i > mxr) rad[i]=_min(rad[(pos<<1)-i],i-mxr); else rad[i]=1; while(s[i-rad[i]] == s[i+rad[i]]) rad[i]++; if(mxr > i-rad[i]) { for(register int j=i-rad[i];j<mxr;j++) lbeg[j]=i; mxr=i-rad[i],pos=i; } } } int main() { scanf("%s",&os[1]); register int ols=strlen(&os[1]),ls=0; s[0]=1,s[++ls]='#'; for(register int i=1;i<=ols;i++) s[++ls]=os[i],s[++ls]='#'; ManacherR(s,ls); register int ans=0; for(register int i=1;i<=ls;i+=2) if(lbeg[i] && rend[i]) ans=_max(ans,lbeg[i]-rend[i]); printf("%d\n",ans); return 0; } |