BZOJ 2565: 最长双回文串 (回文自动机)

2017-11-13 · 2 min read · 回文自动机

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

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

Source

2012国家集训队Round 1 day2

思路：

我们考虑增量构建PAM的时候

构建到pos,当前的状态的len其实就是到以pos位置结尾的最长回文串的长度。

那么我们只需要正着做一遍，再倒着做一遍，然后枚举断点就行了。

时间复杂度O(n)

/* ***********************************************
Author :111qqz
Created Time :2017年11月14日 星期二 01时01分03秒
File Name :2565.cpp
************************************************ */

 1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7struct PAM
 8{
 9    int fail,cnt,len;
10    int nxt[26];
11}st[N];
12char S[N],RS[N];
13int n,now,sz;
14int Right[N],Left[N]; 
15//right[i]表示以i结尾的最长回文串的长度
16//left[i]表示以i开头的最长回文串的长度,需要反转母串构建PAM求得
17void pam_init()
18{
19    ms(st,0);
20    st[0].fail = st[1].fail = 1;
21    st[1].len = -1;
22    sz = 1;
23}
24void extend(char *S,int c,int pos,bool flag)  //忘记加*S这个参数了。。。以至于没有真正反着做orz
25{
26    int p = now;
27    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
28    if (!st[p].nxt[c]){
29    int np=++sz,q=st[p].fail;
30    st[np].len=st[p].len+2;
31    while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
32    st[np].fail=st[q].nxt[c];
33    st[p].nxt[c] = np;
34    }
35    now=st[p].nxt[c];
36    if (flag)
37    Right[pos]=st[now].len;
38    else Left[n-pos-1]=st[now].len;
39    st[now].cnt++;
40}
41int main()
42{
43    #ifndef  ONLINE_JUDGE 
44//  freopen("./in.txt","r",stdin);
45  #endif 
46    scanf("%s",S);
47    pam_init();
48    n = strlen(S);
49    for ( int i = 0 ; i < n; i++) extend(S,S[i]-'a',i,true),RS[n-i-1]=S[i];
50    pam_init();
51    for ( int i = 0 ; i < n; i++) extend(RS,RS[i]-'a',i,false);
52    int ans = 0 ;
53//  for ( int i = 0 ; i < n ; i++) printf("Right:%d Left:%d\n",Right[i],Left[i]);
54    for ( int i = 0 ; i < n-1 ; i++) ans = max(ans,Right[i]+Left[i+1]); //枚举断点
55    printf("%d\n",ans);
56  #ifndef ONLINE_JUDGE  
57  fclose(stdin);
58  #endif
59    return 0;
60}