Manacher 是一种$O(n)$ 求最长回文子串的算法
也可以用于回文串计数

概述

首先把字符串处理成这样子

abab
$#a#b#a#b#
这样保证使偶数长度的回文串中心用#表示,第一个字符防止越界
定义函数p[i]为从i开始最长回文串向一侧的延伸长度

$  # a # b # a # b #
p[i] 1 2 1 3 1 3 1 2 1

可以发现对应到原串中回文串长度恰为 p[i] - 1

现在的问题就是如何$O(n)$求p[i]
记录当前延伸到的最远位置即 mx = p[id] + id (即以id为中心延伸到的最远位置)
若当前匹配位置在最远位置的覆盖中(mx > i),可能有两种情况

  • 完全覆盖 i + p[i] <= mx,p[i] = p[2*id - i] (关于id对称位置)
  • 部分覆盖 i + p[i] > mx,p[i] = mx - i

此后还要从p[i]继续进行匹配

Manacher

代码

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

int convert(char* st, char* dst )
{
int l = strlen(st);
dst[0] = '@';
for (int i = 1;i <= 2*l;i += 2)
{
dst[i] = '#';
dst[i + 1] = st[i/2];
}
dst[2*l+1] = '#';
dst[2*l+2] = '\0';
return 2*l+1;
}

int manacher(char* st, char* dst)
{
int n = convert(st, dst);
int mx = 0, ans = 0, cnt = 0, pos = 0;
for (int i = 1;i <= n;i++ )
{
if (mx > i)
len[i] = min(mx-i,len[2*pos-i]);
else
len[i] = 1;
while(dst[i-len[i]] == dst[i+len[i]]) len[i]++;
if (len[i] + i > mx)
{
mx = len[i]+i;
pos = i;
}
ans = max(ans, len[i]);
//cnt += len[i] / 2;
}
return ans - 1;
//return cnt;
}

题目