马拉车（Manacher）算法是在O（n）时间内解决寻找源字符串的最长回文子串S的问题的算法。
一、插入字符
由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：
在字符串首尾及每个字符间都插入一个 "#"，这样可以使得原先的奇偶回文都变为奇回文；
接着再在首尾两端各插入 "$" 和 "^"，这样中心扩展寻找回文的时候会自动退出循环，不需每次判断是否越界，可参见下面代码。
上述新插入的三个字符，即 "#"、 "$" 和 "^"，必须各异，且不可以与原字符串中的字符相同。
举个例子：s="abbahopxpo"，转换为 s_new="$#a#b#b#a#h#o#p#x#p#o#^"。如此，s 里起初有一个偶回文 abba 和一个奇回文 opxpo，被转换为 #a#b#b#a# 和 #o#p#x#p#o#，长度都转换成了奇数。
二、三个概念
1、回文半径数组
回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度，如下图所示，对于p1所指的位置radius[6]的回文半径是5，每个位置的回文半径组成的数组就是回文数组，所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]。
2、最右回文右边界R
一个位置最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方。比如对于字符串#a#c#b#b#c#b#d#s#，求它的每个位置的过程如下：
最开始的时候R=-1，到p=0的位置，回文就是其本身，最右回文右边界R=0;p=1时，有回文串#a#，R=2；p=2时，R=2;P=3时，R=6;p=4时，最右回文右边界还是p=3时的右边界，R=6,依次类推。
3、最右回文右边界的对称中心C
就是上面提到的最右回文右边界第一次对应的中心点C，如下图，p=4时，R=6，C=3
三、算法过程
由于第一个和最后一个字符都是#号，且也需要搜索回文，为了防止越界，由于字符串在结尾有’\0’，所以在字符串开头需要加上非#号字符(为了区分这里用的$)。通过p数组可以找到最大回文子串半径的最大值及其中心位置，就能确定最长回文子串了。接下来的问题是如何求p数组？
Manacher算法利用开头提到的回文的左边是右边的镜像，让回文串起始的对比位置尽可能的大。
图注：id为已知的最大回文子串中心的位置，mx是已知最大回文串的右边界，i为当前遍历到字符串的位置。
这里有两种情况讨论：
1、mx>i
2、mx<i
此时镜像对预判位置起不到作用，只能从长度为1开始对比，所以p[i] = 1。
四、代码
```
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j++] = '^'; // 别忘了哦
s_new[j] = '\0'; // 这是一个好习惯
return j; // 返回 s_new 的长度
}
int Manacher()
{
int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1; // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i); // 需搞清楚上面那张图含义，mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]]) // 不需边界判断，因为左有 $，右有 ^
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，
// 这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main()
{
while (printf("请输入字符串："))
{
scanf("%s", s);
printf("最长回文长度为 %d\n\n", Manacher());
}
return 0;
}
```
```
请输入字符串：abbahopxpo
最长回文长度为 5
请输入字符串：a
最长回文长度为 1
请输入字符串：aa
最长回文长度为 2
请输入字符串：abax
最长回文长度为 3
```
