「Luogu P4555」[国家集训队]最长双回文串

发表于 |
字数统计: 525 | 阅读时长 ≈ 2

给定一个串$S$，求$S$中最长的子串$T$，使得可以将$T$分为两个长度大于等于$1$的回文串，只需输出$T$的长度即可。

$\texttt{Data Range:}2\leq \vert S\vert \leq 10^5$

很明显的回文树题。只是因为窝不会马拉车

考虑枚举分的位置，假设以这个位置结尾的回文子串为$X$，这个位置开头的回文子串为$Y$，那么有

贪心地考虑，如果这个$X$或者$Y$的长度不是最大的话，那么它绝对不是答案，因为$X$或者$Y$还可以继续扩展。所以，这个位置的答案为$\max\{\vert X\vert +\vert Y\vert\}$。

于是预处理出位置$i$的$pre_i=\max\{\vert X\vert\}$和$suf_i=\max\{\vert Y\vert\}$。

然后很明显的扫一遍，求出$\max\{pre_i+suf_{i+1}\}$就好了。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=2e5+51;
ll length,res;
ll prefix[MAXN],suffix[MAXN]; 
char str[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
namespace PalindromicTree{
	const ll sigmaSize=27;
	struct Node{
		ll son[sigmaSize];
		ll fa,length;
	};
	struct PalindromicTree{
		Node nd[MAXN];
		ll last,tot;
		PalindromicTree()
		{
			nd[0].fa=nd[1].fa=1;
			nd[tot=1].length=-1;
		}
		inline void extend(ll ch,ll length,char *str)
		{
			ll p=last,nxt,k;
			while(str[length-nd[p].length-1]!=str[length])
			{
				p=nd[p].fa;		
			}	
			if(!nd[p].son[ch])
			{
				nxt=++tot,k=nd[p].fa;
				nd[nxt].length=nd[p].length+2;
				while(str[length-nd[k].length-1]!=str[length])
				{
					k=nd[k].fa;		
				}
				nd[nxt].fa=nd[k].son[ch],nd[p].son[ch]=nxt;
			}
			last=nd[p].son[ch];
		}
	};
}
PalindromicTree::PalindromicTree pt,pt2;
int main()
{
	scanf("%s",str+1),length=strlen(str+1);
	for(register int i=1;i<=length;i++)
	{
		pt.extend(str[i]-97,i,str),prefix[i]=pt.nd[pt.last].length;
	}
	reverse(&str[1],&str[length+1]);
	for(register int i=1;i<=length;i++)
	{
		pt2.extend(str[i]-97,i,str),suffix[length-i+1]=pt2.nd[pt2.last].length;
	}
	for(register int i=1;i<length;i++)
	{
		res=max(res,prefix[i]+suffix[i+1]);
	}
	printf("%d",res);
}