RT
模板题：
给出一个只由小写英文字符 组成的字符串 ,求 中最长回文串的长度 。
字符串长度为 。
首先，可以发现回文串的长度可以是奇数也可以是偶数，其中奇数串的回文对称中心是串中的一个字符，而偶数串的回文对称中心是两个字符之间的空隙，如
和
为了避免分类讨论，我们在每两个字符中间插入一个特殊字符 #，使得所有回文串的对称中心都在某一个字符上。其中奇数串对称中心不变，偶数串对称中心变为 #。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| const int maxn = 3e7;
char str[maxn];
int len = 0;
void read() {
int ch = getchar();
while (ch >= 'a' && ch <= 'z') {
str[++len] = '#';
str[++len] = ch;
ch = getchar();
}
str[++len] = '#';
return;
}
|
变化之后，得到的所有最长回文串长度都为奇数（设为 ），我们称 为它的半径。
分别考虑回文对称中心为 # 与不为 # 的最长回文串，可以发现原回文串的长度刚好等于变化后回文串的半径。
回到问题，容易想到一种 的算法，即尝试以每一个字符作为对称中心向左右同时拓展。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| inline bool valid(int pos) {
return pos > 0 && pos <= len;
}
int main() {
read();
int ans = 0;
for (int ctr = 1; ctr <= len; ctr++) {
int l = 1;
while (valid(ctr+l) && valid(ctr-l) && str[ctr+l] == str[ctr-l]) l++;
l--;
ans = max(ans, l);
}
printf("%d\n", ans);
return 0;
}
|
这样的算法面对 的数据范围显然有点吃力，于是线性时间的 算法闪亮登场。
在每次选取对称中心时，我们都要向左右两边同时拓展，当前对称中心右边的点在将来会被选为对称中心，当前对称中心左边的点已被选为对称中心进行拓展过，如果当前对称中心右边某点处于当前对称中心所能拓展的最长回文串内，我们就可以借助这回文串的对称性来减少计算量。
先假设以下字母（以下字母均表示字符编号）：
- 为目前要处理的字符，
- 为 前某点，以其为对称中心的最长回文串包含了 ，
- 为 能拓展到的最右端字符，
- 为 关于 对称的字符，
- 为以 为对称中心的最长回文串半径。
接下来分情况讨论：
显然，这时以 为中心的最长回文串半径 。
此时，我们可以直接从 开始向右拓展。
看起来不错，但是还有一个问题：我们的程序显然应该遍历的是 ，那 从何而来呢？
想一想我们对 的要求：唯一的要求是，以 为中心的最长回文串的右边界应尽量靠右，以尽量达成 ，在此前提下， 应尽量靠左。
所以， 我们不如直接以目前拓展过的最右边界（）来确定 ：若当前字符 拓展的最右边界在 右边，则令 ，同时更新 。
现在 成了与 无关的量，我们补上第三种情况：
（即 ）
暴力拓展即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int l[maxn];
int main() {
read();
int ans = 0, mid = 0, mr = 0;
for (int i = 1; i <= len; i++) {
if (i > mr) l[i] = 1;
else {
int j = 2 * mid - i;
l[i] = min(mr - i + 1, l[j]);
}
while (valid(i+l[i]) && valid(i-l[i]) && str[i-l[i]] == str[i+l[i]]) l[i]++;
l[i]--;
if (i + l[i] > mr) mr = i + l[i], mid = i;
ans = max(ans, l[i]);
}
printf("%d\n", ans);
return 0;
}
|
可以在串的首尾加上不同的特殊字符，以避免边界判断。完整代码如下：
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
| #include <cstdio>
#include <algorithm>
using std::max;
using std::min;
const int maxn = 3e7;
char str[maxn];
int len;
int l[maxn];
void read() {
int ch = getchar();
while (ch >= 'a' && ch <= 'z') {
str[++len] = '#';
str[++len] = ch;
ch = getchar();
}
str[++len] = '#';
str[0] = '~', str[len+1] = '@';
return;
}
int main() {
read();
int ans = 0, mid = 0, mr = 0;
for (int i = 1; i <= len; i++) {
if (i > mr) l[i] = 1;
else {
int j = 2 * mid - i;
l[i] = min(mr - i + 1, l[j]);
}
while (str[i-l[i]] == str[i+l[i]]) l[i]++;
l[i]--;
if (i + l[i] > mr) mr = i + l[i], mid = i;
ans = max(ans, l[i]);
}
printf("%d\n", ans);
return 0;
}
|