Manacher（马拉车）算法
问题：
- 在字符串中，找出所有的回文子串；
- 在字符串中，找出最长的回文子串； 两个问题可以结合解决。
1.相关概念引入
1.回文字符串： 正着读和反着读都一样的字符串就是回文字符串。 2.回文子串： 一个字符串的某个字串是回文。 3.奇回文串： 回文串的字符数为奇数。 4.偶回文串： 回文串的字符数为偶数。 5.回文中心： c，回文串最中心的位置。奇回文串（回文中心）：n + 1 / 2; 偶回文串（回文中心）：n / 2 与 n/2 + 1 之间 6.回文半径： d，回文中心到回文半径左/右端点的距离（字符数，包括本身）。
2.中心扩展算法
算法原理
- 从前往后遍历字符串，以 s[i] 或 s[i] 与 s[i + 1] 的中间作为回文串的中心位置；
- 从中间位置开始，枚举半径长度，逐渐向两边扩展，找出以该点为中心的最长的回文子串。
预处理
为了防止对奇偶回文字串进行分类讨论，且奇回文字串更好处理，这里将其统一转化为奇回文串。 预处理字符串： 在相邻字符之间和整个字符串的两端任意加入一个字符 '#'。 例如，字符串 s = "abcbaa" 经过预处理之后就变成：s = "#a#b#c#b#a#a#"。 经过预处理之后： 本来是奇回文串，处理之后依旧是奇回文串。例如 "bab" 处理后为 "#b#a#b#"； 本来是偶回文串，处理之后就变成奇回文串。例如 "abba" 处理后为 "#a#b#b#a#"； 此时，在处理之后的串上跑中心扩展算法时，由于所有的回文串都是奇回文串，仅需枚举所有中心点，即可找到所有的回文串。
注意： （不用像 kmp 算法那样，加入一个不会出现的字符，这里可以加入任意字符。 因为判断回文的时候，只会原始字符和原始字符判断，新加入的字符和新加入的字符判断。因此，可以加入任意字符。）
代码：
string t, s;
int m, n;
// 以求解最长回文子串为例
int fun(){
// 预处理字符串
cin >> t;
m = t.size();
s += ' '; // 这里要处理边界不同，' ' != '#'
for(auto ch : t){
s += '#';
s += ch;
}
s += "##";
n = s.size()-2;
int ret = 1;
// 中心扩展算法
for(int i = 1; i <= n; i++){
int d = 1; // 枚举向右向左的距离
while(s[i - d] == s[i + d]) d++;
ret = max(ret, d - 1);
}
return ret;
}
时间复杂度：O(n^2)
3.Manacher 算法
概念引入
1.回文半径数组： d[i] (以 i 为中心的最长回文半径)。 例如，字符串"#a#a#a#b#a#", 回文半径数组：
| 字符串 | # | a | # | a | # | a | # | b | # | a | # |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 回文半径 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 4 | 1 | 2 | 1 |
2.两个重要的性质：
- 回文串的长度为 d[i] - 1;
- 以 i 为中心的回文串有 d[i] / 2 个。
3.加速盒子（最右回文串）： 从前往后填表的过程中，区间 [l, r], 找到右端点最靠右的回文子串，不断维护区间。 它可以帮助我们加速填表。 如："#a#a#a#b#a#"； 依次维护的区间：[1, 1] -> [1, 3] -> [1, 5] -> [1, 7] -> [1, 7] -> [1, 7] -> [1, 7] -> [5, 11] -> [5, 11]
4.【Manacher 算法 - 利用最右回文串加速更新回文半径数组】
分类讨论（核心）
从前往后填表，当填到 d[i] 时，d[1] ~ d[i - 1] 均已经填好，并且维护最右回文串 [l, r]。当填写时，分下面大类，四种情况讨论：
-
i > r, 当前点没有在最右回文串中。此时，d[1] ~ d[i - 1] 的回文信息提供不了任何帮助。直接以 i 为中心暴力扩展（与中心扩展算法一致）；
-
i <= r, 当前点在最右回文串中，由对称性可知，j - l = r - i, 对称点 j = r - i + l 的回文半径 d[j], 分为一下三种情况进行讨论：
a. d[j] < r - i + 1（最长回文半径），即以 j 为中心的最长回文串包含在 [l, r] 内: 由对称性可知，d[i] = d[j] = d[r - i + l]
b. d[j] > r - i + 1，即以 j 为中心的最长回文串的左边界越过了 l: d[i] = r - i + 1。
c. d[j] = r - i = 1，即以 j 为中心的最长回文串的左边界正好在 l 位置： 此时 d[i] 至少为 d[j],且还可能往外扩展。就可以从 d[j] 开始，用中心扩展算法暴力向外扩展。
注意这里：1 和 2.c 情况还会涉及到对最右回文串区间 [l, r] 的更新。
时间复杂度：注意到，在整个算法执行的过程中 r 是不会回退的，相当于 i, r 两个指针不回退的向后移动。 因此整个时间复杂度为 O(n)。
代码实现： 这里非常的精妙，可以把 4 种情况都考虑进去。
string t, s;
int n, d[N];
// 预处理
void init(){
cin >> t;
s = ' ';
for(auto ch : t){
s += '#';
s += ch;
}
s += "##";
n = s.size()-2;
}
void get_d(){
d[1]=1;
for(int i =2, l =1, r =1; i <= n; i++){
int len = r >= i ? min(d[r - i + l], r - i +1):1;//=1 是第 1 种情况，d[r - i + 1] 是第 2，r - i + 1 是第 3，两个相等，任取一个是第 4。
while(s[i + len]== s[i -len]) len++;//1，4 会进入循环，执行中心扩展算法，2，3 会判断不等
if(i + len -1> r) r = i + len -1, l = i - len +1;// 更新区间
d[i]= len;
}
}
4.算法模板
代码：
#include<iostream>
using namespace std;
const int N = 2.2e7+10;
string t, s;
int m, n;
int d[N];
int main(){
cin >> t;
m = t.size();
s += ' ';
for(auto ch : t){
s += '#';
s += ch;
}
s += "##";//处理边界要不同
n = s.size()-2;
d[1]=1;
int ret =1;
for(int i =2, l =1, r =1; i <= n; i++)// 这里初始化，不能在内 {
int len = r >= i ? min(d[r - i + l], r - i +1):1;
while(s[i + len]== s[i - len]) len++;
if(i + len -1> r) r = i + len -1, l = i - len +1;
d[i]= len;
ret =max(ret, d[i]-1);
}
cout << ret << endl;
return 0;
}
