P4555-[国家集训队]最长双回文串
题目:
题目描述:
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。
输入长度为$n$的串$S$，求$S$的最长双回文子串$T$,即可将$T$分为两部分$X$，$Y$，（$|X|,|Y|≥1$）且$X$和$Y$都是回文串。
输入格式:
一行由小写英文字母组成的字符串$S$。
输出格式:
一行一个整数，表示最长双回文子串的长度。
样例:
样例输入1:
样例输出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
| // Problem: P4555 [国家集训队]最长双回文串
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4555
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
const int maxn = 2e5 + 10;
char s[maxn << 1], t[maxn << 1];
int p[maxn], l[maxn], r[maxn];
int mx, n, id;
int main()
{
yin >> (t + 1);
n = strlen(t + 1);
int cnt = 0;
s[++cnt] = '$', s[++cnt] = '#';
for (int i = 1; i <= n; i++)
s[++cnt] = t[i], s[++cnt] = '#';
s[++cnt] = '\0';
n = cnt;
// puts(s + 1);
// n = 2 * n + 1;
for (int i = 1; i <= n; i++)
{
if (i < mx)
p[i] = min(p[id * 2 - i], mx - i);
else
p[i] = 1;
while (s[i - p[i]] == s[i + p[i]])
p[i]++;
if (mx < i + p[i])
id = i, mx = i + p[i];
l[i + p[i] - 1] = max(l[i + p[i] - 1], p[i] - 1);
r[i - p[i] + 1] = max(r[i - p[i] + 1], p[i] - 1);
}
for (int i = 2; i <= n; i += 2)
{
if (i > 1)
r[i] = max(r[i], r[i - 2] - 2);
// cerr << i << " " << r[i] << endl;
}
for (int i = n; i >= 2; i -= 2)
{
l[i] = max(l[i], l[i + 2] - 2);
// cerr << i << " " << l[i] << endl;
}
int ans = 0;
for (int i = 2; i <= n; i += 2)
if (r[i] && l[i])
ans = max(ans, l[i] + r[i]);
yout << ans << endl;
return 0;
}
|