P4287-[SHOI2011]双倍回文
题目:
题目描述:
记字符串$w$的倒置为$w^R$。例如$(abcd)^R=dcba$，$(abba)^R=abba$。
对字符串x，如果$x$满足$x^R=x$，则称之为回文；例如abba是一个回文，而abed不是。
如果x能够写成的$ww^Rww^R$形式，则称它是一个“双倍回文”。换句话说，若要$x$是双倍回文，它的长度必须是$4$的倍数，而且$x$，$x$的前半部分，$x$的后半部分都要是回文。例如$abbaabba$是一个双倍回文，而$abaaba$不是，因为它的长度不是4的倍数。
$x$的子串是指在$x$中连续的一段字符所组成的字符串。例如$be$是$abed$的子串，而$ac$不是。
$x$的回文子串，就是指满足回文性质的$x$的子串。
$x$的双倍回文子串，就是指满足双倍回文性质的$x$的子串。
你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。
输入格式:
输入分为两行。
第一行为一个整数，表示字符串的长度。
第二行有个连续的小写的英文字符，表示字符串的内容。
输出格式:
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出$0$。
样例:
样例输入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
| // Problem: P4287 [SHOI2011]双倍回文
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4287
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e6 + 5;
int n, f[N], ans;
char a[N], s[N];
int main()
{
scanf("%d%s", &n, a + 1);
s[0] = '~';
for (int i = 1; i <= n; i++)
s[i * 2 - 1] = '#', s[i * 2] = a[i];
s[n * 2 + 1] = '#';
for (int i = 1, r = 0, c = 0; i <= n * 2; i += 2)
{
f[i] = i < r ? min(f[c * 2 - i], r - i) : 1;
if (i < r && i - f[i] < c)
ans = max(ans, i - c << 1);
while (s[i - f[i]] == s[i + f[i]])
f[i]++;
if (i + f[i] > r)
r = i + f[i], c = i;
}
printf("%d\n", ans);
return 0;
}
|