马拉车算法是一个高效求解最长回文子串的算法。
传统的暴力方法是枚举回文子串中点，向两端扩展至无法继续扩展时更新答案，复杂度是 \(O(n^2)\) 的，效率并不算高。
我们注意到，回文串具有对称性，能不能利用这个性质减少运算量呢？
首先我们要对原来的字符串做点小小的处理。回文串的长度可能是偶数，这种情况下枚举回文串的中点非常难搞。
我们可以在原字符串的相邻两个字符之间，以及字符串最前面和最后面插入一些其他字符（比如说#号），这样所有回文串的长度就都是奇数啦！
QAQQwQ
->#Q#A#Q#Q#w#Q#
我们定义 \(f_i\) 表示以 \(i\) 为对称中心的回文串的最大半径（即从中心到最左/右端的长度），\(maxr\) 表示目前已经访问到的最右端的字符，\(mid\) 表示右端为 \(maxr\) 的最长回文子串的对称中心。
和传统算法一样，我们还是从左到右枚举对称中心 \(i\)。但是我们可以利用回文串的对称性减少一部分运算量。
当 \(i<maxr\) 时，我们可以利用之前已经算出来的信息来减少运算量。
设 \(i\) 关于 \(mid\) 的对称点为 \(j=2 \times mid-i\)。这时，根据 \(mid\) 的定义，我们可以直接将 \(f_i\) 的值设置成 \(f_j\)。当然，考虑到 \(i+f_i \leq maxf\) 的这一性质，实际上：
$$f_i=\min(f_j,f_{mid}+mid-i)$$
如果\(i>maxr\)，以前的信息就没有用了，\(f_i=1\)。
接下来，我们还是采用传统的暴力方法向两端扩展，同时更新\(f_i,mid,maxr\)。
马拉车的时间复杂度？乍一看并不显然。
因为 \(maxr\) 最多右移 \(n\)，复杂度是 \(O(n)\)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[11000005],s[25000005];
int f[25000005];
void init()
{
s[0]=s[1]='#';//0位置防止越界
int len=strlen(a);
for(int i=0;i<len;i++)
{
s[2*i+2]=a[i];
s[2*i+3]='#';
}
s[2*len+2]=0;
}
int main()
{
int ans=0;
scanf("%s",a);
init();
int len=strlen(s),maxr=0,mid=0;
for(int i=1;i<len;i++)
{
if(i<maxr)
f[i]=min(f[mid]+(mid-i),f[mid*2-i]);
else f[i]=1;
while(s[i+f[i]]==s[i-f[i]])
f[i]++;
if(f[i]+i>maxr)
{
maxr=f[i]+i;
mid=i;
}
ans=max(ans,f[i]);
}
printf("%d\n",ans-1);
return 0;
}