51nod 1395 两个回文 题解

题意简述

多组数据。每次给定一个字符串$S$,$|S|<=1e5$,请从$S$中选择两个不相交的回文子串使得这两个子串的长度和最大。

思路框架

对于每个位置,求出前缀和后缀中最长回文子串。然后枚举断点,更新答案。

具体思路

首先考虑如何求出前缀和后缀中的最长回文子串。

然后我们珂以先求最长回文后缀(简称$LPS$,即$Longest Palindrome Suffix$)和最长回文前缀(简称$LPP$,即$Longest Palindrome Prefix$)。$LPS[i]$表示以$i$为结尾的前缀的最长回文后缀,$LPP[i]$表示以$i$开头的后缀的最长回文前缀。然后,只要求$LPS$的前缀最大值,$LPP$的后缀最大值,就是前缀/后缀中的最长回文子串了。

$LPP$和$LPS$都很好求,就是回文自动机的板子。正着跑一遍求出$LPS$,反着跑一遍求出$LPP$。

原地修改前缀/后缀最大值。然后用$LPS[i]+LPP[i+1]$更新答案即珂。这个式子的含义是:一个回文子串在$i$左边,一个回文子串在$i$右边,也就是上文说的“枚举断点”。

提示

代码很长,从Soviet函数开始看代码哦,这样方便理清结构。

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
#define N 155555
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)

char s[N];int n;
void Input()
{
scanf("%s",s+1);n=strlen(s+1);
}

class Palindrome_Tree
{
public:
char s[N];
struct node
{
int len,fail;
int ch[26];
}t[N];
node& operator[](int id){return *(t+id);}
int last;
int cnt=1;
void Init(char ss[N])
{
FK(t);
strcpy(s+1,ss+1);
t[0].len=0;t[0].fail=1;
t[1].len=-1;t[1].fail=0;
cnt=1;
last=0;
}

int Getfail(int fa,int pos)
{
int cur=t[fa].fail;
for(;s[pos]!=s[pos-t[cur].len-1];cur=t[cur].fail);

int id=s[pos]-'a';return t[cur].ch[id];
}
void Insert(int pos)
{
int cur=last;
while(s[pos-t[cur].len-1]!=s[pos])
{
cur=t[cur].fail;
}

int id=s[pos]-'a';
if (t[cur].ch[id]==0)
{
++cnt;
t[cnt].len=t[cur].len+2;
t[cnt].fail=Getfail(cur,pos);
t[cur].ch[id]=cnt;
}
last=t[cur].ch[id];
}
}T; //普通的回文自动机

int LPS[N],LPP[N];
void Soviet()
{
FK(LPS),FK(LPP);
T.Init(s);F(i,1,n) T.Insert(i),LPS[i]=T[T.last].len;//正着跑一遍求出LPS,以i结尾的前缀的最长回文后缀

reverse(s+1,s+n+1);
T.Init(s);F(i,1,n) T.Insert(i),LPP[n-i+1]=T[T.last].len; //反着跑一遍LPP,以i开始的后缀的最长回文前缀

F(i,1,n) LPS[i]=max(LPS[i],LPS[i-1]); //以i结尾的前缀的最长回文子串
D(i,n,1) LPP[i]=max(LPP[i],LPP[i+1]); //以i开头的后缀的最长回文子串

int ans=0;
F(i,1,n-1) ans=max(ans,LPS[i]+LPP[i+1]);//枚举断点
printf("%d\n",ans);
}

#define Flan void
Flan IsMyWife()
{
int t;cin>>t;
while(t--)
{
Input();
Soviet();
}
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();getchar();
return 0;
}
w