基本概念
1. 改造字符串
在字符之间和两端插入一个不存在于原字符串中的字符,例如向字母串中插入 '#'
, 使得改造后的字符串都变成 奇回文串,方便统一处理。字符串下标从1开始,将s[0]设为'$'
用作哨兵。
char a[N], s[N];
int n = strlen(a + 1), k = 0;
s[0] = '$', s[++k] = '#';
for(int i = 1; i <= n; ++i)
{
s[++k] = a[i];s[++k] = '#';
}
n = k;
// before: aba
// after: $#a#b#a#
2. 回文半径d[i]
以i为中心的最长回文串长度的一半称为回文半径。
i 0 1 2 3 4 5 6 7
s[i] $ # a # b # a #
d[i] 1 2 1 4 1 2 1
3. 加速盒子l, r
s[l]
到 s[r]
维护了右端点最靠右的最长回文串。利用盒子可以更快速地求得 d[i]
(盒子内对称点 d[i]
相等)
算法流程
计算完前i - 1
个d
函数,维护加速盒子l, r
- 如果$i <= r$(在加速盒子内),i的盒内对称点为l + (r - i)
(1)如果d[l + (r - i)] < r - i + 1
,即以i为中心的最长回文串限制在盒内,由于d[i]
和d[l + (r - i)]
是关于盒中心对称的,所以直接赋值即可:d[i] = d[l + (r - i)]
(2)如果d[l + (r - i)] >= r - i + 1
, 先取盒内一定对称的部分,再暴力拓展盒子外的部分:d[i] = r - i + 1
- 如果$i > r$ (在加速盒子外), 则从i向两侧开始暴力枚举
- 求出
d[i]
后,如果i + d[i] - 1
(以s[i]
为中心的最长回文串的右端点)大于r
, 则更新l = i - d[i] + 1, r = i + d[i] - 1
。
void getd(char * s, int n)
{
d[1] = 1;
for(int i = 2; l,r = 1; i <= n; ++i)
{
if(i <= r)d[i] = min(d[r - i + l], r - i + 1);
while(s[i - d[i]] == s[i + d[i]])d[i] ++;
if(i + d[i] - 1 > r)l = i - d[i] + 1, r = i + d[i] - 1;
}
}
最长回文子串的长度为max{d[i]} - 1