前言
马拉车算法是一个能在线性时间能求出最长回文串长度的算法。
个人感觉和kmp也许有异曲同工之妙。
首先，我们的目标是求出最长回文子串的长度。
暴力相信大家都会，先是枚举 L 和 R 然后 $O(n)$ 判断每个子串是否是回文串，总时间复杂度 $O(n^3)$。
稍微优化一下，枚举中间点 mid,贪心地向两端扩展找到最长的 $len_i$，即以 $i$ 为回文串中心的最大扩展长度。当然，我们发现这样只能处理回文串长度为奇数的情况。所以对于这个暴力，我们有了一个新思路：在两个相邻字符之间插入一个不会出现的字符。
比如 aabba，我们把它变成 #a#a#b#b#a#，这样每个点向两边扩展出的就一定是奇数长度的 $len_i$ 了。于是这个暴力的时间复杂度就是 $O(n^2)$。下面所使用的字符串也是经过了这样的变换的。
这也正打开了马拉车算法的大门。
众所周知，对暴力算法的优化是对重复计算的优化以及已知信息的利用。
先来看重复的计算。
在上面 $O(n^2)$ 的算法中，我们对很多子串进行了重复搜索，最明显的就是，假设 $i$ 和 $j$ 都在同一个回文子串内并且关于中心对称，那么 $len_j\ge len_i$。这是显然的。
于是我们考虑设置一个变量 $mid$，表示上面那个回文子串的中心，$mr(maxright)$ 表示这个回文子串的右端点。
哦对了，这个回文子串是当前右端点最大的回文子串，所以叫做 $maxright$。
当我们目前遍历到的 $i$ 是小于 $mr$ 的时候，即下图这种情况。
如图，我们找到 $i$ 的对称点 $i'$，发现可以用 2*mid-i 得到，于是 len[i]=len[mid*2-i]，但是这个对称只在我们以 $mid$ 为重心的回文串中可以用，所以 i+len[i]<=mr,len[i]<=mr-i，综合，len[i]=min(len[mid*2-i],mr-i)。
接下来是另一种情况，也就是 $i$ 在 $mr$ 的右边，$i\ge mr$。
此时，我们没有多余的信息可以利用了，只能以 $i$ 为重心开始和上面说的一样暴力地拓展找 $len_i$，那么此时我们的 $i$ 就是新的 $mid$，找到的 $i+len_i$ 就是新的 $mr$。
那么这样的时间复杂度为什么是 $O(n)$ 的呢？
如果 $i+len_i'\leq mr$，那么是不能向右扩展的，否则扩展 $mr$ 计入均摊时间。
于是总的时间复杂度就是 $O(n)$。
模板题代码；
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define reg register
using namespace std;
const int N=2.2e7+10;
char d[N];
int hw[N],n;
void read(){
char ch=getchar();
d[0]=d[++n]='#';
while(ch<'a'||ch>'z')ch=getchar();
while(ch>='a'&&ch<='z')d[++n]=ch,d[++n]='#',ch=getchar();
}
void manacher(){
int mr=0,mid;
for(int i=1;i<n;i++){
if(i<mr)hw[i]=min(hw[(mid<<1)-i],mid+hw[mid]-i);
else hw[i]=1;
while(d[i+hw[i]]==d[i-hw[i]])hw[i]++;
if(i+hw[i]>mr)mr=hw[i]+i,mid=i;
}
}
int main(){
int ans=1;
read();
manacher();
for(int i=0;i<n;i++)
ans=max(ans,hw[i]);
printf("%d\n",ans-1);
return 0;
}