首页 > 代码库 > bzoj2565 最长双回文串

bzoj2565 最长双回文串

2024-09-22 16:50:42   215人阅读

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

 

正解：回文自动机。

正反构造两个回文自动机，顺便记录以当前点为终点的最长回文后缀。然后直接枚举端点，取和的$max$即可。

 

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define inf (1<<30)15 #define N (200010)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 int ans;24 25 struct PAM{26 27     int ch[N][26],fa[N],l[N],len[N],n,la,sz;28     char s[N];29 30     il void pre(){ l[++sz]=-1,fa[0]=1; return; }31 32     il void add(RG int c,RG int n){33     RG int x=la; while (s[n-l[x]-1]!=s[n]) x=fa[x];34     if (!ch[x][c]){35         RG int v=++sz,k=fa[x]; l[v]=l[x]+2;36         while (s[n-l[k]-1]!=s[n]) k=fa[k];37         fa[v]=ch[k][c],ch[x][c]=v;38     }39     la=ch[x][c],len[n]=l[ch[x][c]]; return;40     }41     42 }tr1,tr2;43 44 il void work(){45     scanf("%s",tr1.s+1),tr1.n=strlen(tr1.s+1),tr2.n=tr1.n,tr1.pre();46     for (RG int i=1;i<=tr2.n;++i) tr2.s[i]=tr1.s[tr1.n-i+1]; tr2.pre();47     for (RG int i=1;i<=tr1.n;++i)48     tr1.add(tr1.s[i]-97,i);49     for (RG int i=1;i<=tr2.n;++i) tr2.add(tr2.s[i]-97,i);50     for (RG int i=1;i<tr1.n;++i) ans=max(ans,tr1.len[i]+tr2.len[tr2.n-i]);51     printf("%d\n",ans); return;52 }53 54 int main(){55     File("PAM");56     work();57     return 0;58 }

 

bzoj2565 最长双回文串


联系
我们