Manacher 入门
Yamchip
·
·
算法·理论
前言
这个算法真的比 KMP 简单。
描述
给定一个长度为 n 的字符串 S，求字符串 S 的最长回文子串长度。
1. 暴力
可以使用中心扩展法，对于回文串，枚举中心点，在往两端扩展。要分类讨论奇偶性，总复杂度 O(n^{2})。
给出部分代码。
长度为奇数
int k = 0;
while(s[i - k] == s[i + k]) k++;
长度为偶数
int l = 0, r = 1;
while(s[i - l] == s[i + r]) l++, r++;
2. 优化
Part1
可以发现，每次检查回文都会重复计算，于是可以参考 KMP 的思路，跳过已检查过的点。
Part2
在进行中心扩展时，要分类讨论字符串长度的奇偶性。那在 Manacher 中如何避免呢？在字符串 S 中插入一种 S 中没有的字符，可以用 #。
举个例子，把 "abcab" 操作后变成 "#a#b#c#a#b#"。为了防止越界，要在两端加上两个不同的奇怪字符。不同是为了防止检查回文时多匹配。
这种方法是如何避免奇偶性讨论的，可以自行思考。
3. 正式优化
定义数组 P[0...n]，P[i] 为以 S[i] 为中心点的最长回文串的半径。
Manacher 的核心思想是“回文的镜像也是回文”。如图，已经求出了 P[C]。则它左边的阴影部分是以 j 为中心的回文，由于回文是对称的，所以右边的镜像部分 i 与 回文 j 相同，那么在计算以 s[i] 为中心时，可以直接从长度 P[j] 开始匹配。然而这只是一种情况，下面是 Manacher 的完整思路。
假设已经求出了 p[0]\sim p[i-1]，现在求 P[i]。定义 C 为 p[0]\sim p[i-1] 这些回文串中最大的中心点，R 为 C 对应的回文串的右端点。那么 R 就等于 C + P[C]，且 R 是已检查字符串的右端点。通俗的说，R 左边的都检查过，右边的都没检查。
现在有两种情况。
$i < R$ 这种情况，又可以细分为两种小情况。
1. 上文叙述了这种情况，这里仅做补充。如何得知 $j$ 的位置？因为 $\frac{i + j}{2} = C$，所以 $j = 2C - i$。然后对 $i$ 进行中心扩展即可。
2.当 $j$ 的回文在 $C$ 对应字符串的外部时，那么由图可知，$i$ 可确定的回文也只有 $i$ 到 $R$ 这段了，当然这段长度是 $R-i$，所以以这段为基础进行中心扩展即可。
## 4. 答案
举个例子就明白了：`#a#b#b#a#` `#a#b#c#b#a#`
观察可以得到，答案即为半径减一。
## 5.模板
[ 【模板】manacher](https://www.luogu.com.cn/problem/P3805) & [高手过愚人节](https://www.luogu.com.cn/problem/P1723)
可以先消化完上面的内容再来做。因为上文讲的很清楚了，这里只给出代码。
```cpp
void manacher(char *t)
{
int r = 0, c = 0;
for(int i = 0;i < n;i++)
{
if(i < r) p[i] = min(p[(c << 1) - i], r - i);
else p[i] = 1;
while(t[i - p[i]] == t[i + p[i]]) p[i]++;
if(i + p[i] > r)
{
r = i + p[i];
c = i;
}
}
}
```
## 6.应用
[ [国家集训队] 最长双回文串 ](https://www.luogu.com.cn/problem/P4555)
题意很好理解，看到最长回文子串显然可以想到 Manacher。可以观察到双回文子串就是两个回文子串，于是把双回文子串分成两部分。统计以这位为结尾或开头的最长回文子串。这部分可以在中心扩展时维护。答案即为两者相加。
### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, ans, p[N << 1], l[N << 1], r[N << 1];
string s, t;
void manacher(string t)
{
int n = t.size();
int R = 0, c = 0;
for(int i = 0;i < n;i++)
{
if(i < R) p[i] = min(p[(c << 1) - i], R - i);
else p[i] = 1;
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);
while(t[i - p[i]] == t[i + p[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);
}
if(i + p[i] > R)
{
R = i + p[i];
c = i;
}
}
}
int main()
{
cin >> s;
n = s.size();
t = "$#";
for(int i = 0;i < n;i++)
{
t.push_back(s[i]);
t.push_back('#');
}
t.push_back('&');
manacher(t);
n = t.size();
for(int i = 3;i < n - 2;i++)
if(t[i] == '#')
ans = max(ans, l[i] + r[i]);
cout << ans;
return 0;
}
```
## 7.习题
[ [国家集训队] 拉拉队排练](https://www.luogu.com.cn/problem/P1659)
[ [THUPC2018] 绿绿和串串](https://www.luogu.com.cn/problem/P5446)
[ 回文匹配](https://www.luogu.com.cn/problem/P6216)