一个求回文数或者回文子串的算法。
1975年，一个叫Manacher发明了Manacher Algorithm算法，俗称马拉车算法，其时间复杂为O(n)。该算法是利用回文串的特性来避免重复计算的，至于如何利用，这篇博客自己阐述一下自己的理解。
-
首先对于字符串$S$,为了方便处理，我们将$S$的首尾和中间都加上#号，比如$S=”abba”$，我们将其转换为S=#$a$#$b$#$b$#$a$#，如果$S=”a“$,我们将其转换为$S=$#$a$#。这样子偶数的字符串和奇数字符串统一转换为奇数字符串。
-
下面举个例子，我们定义以这个元素为中心的最长回文半径的数组为$P[]$，其中$P[i]-1$就是该元素在原先的$S$中回文子串的长度。
简单的说明一下，对于元素$s$，它的回文半径为$P[i]$,那么它的回文长度为$2*P[i]-1$,观察数组可以知道，对于任何一个这样子的回文子串#的数量就是$P[i]$，$P[i]-1$就是它在S的回文子串的长度。
由于需要计算P[0],P[len-1]需要用到P[-1]，和P[len]，为了防止越界，在S前面加一个不是#的字符，由于S默认以‘\0’结尾，S[len]一般不会报错，所以不用增加了
- 计算数组$P$，这里很类似KMP，利用前面的结果，来计算后面的结果。从左到右一次计算，并且$Mi$表示之前取得的最大回文串的中心位置，而R是能到达的最右端的值。
3.1 当i>=R时，无法利用回文串特性，因此只能老老实实的一步步匹配。
3.2 当$i<R$时，如下图
当$P[j]<R-i$时，$P[i]$的初始值就不是1，就是$P[j]$
当$P[j]>=R-i$时，那么$P[j]$的左端超过了$R$，此时$P[i]$的初始值为$R-i$
下面直接展示代码
int getMax(string s){
//怕越界 主要是有一个ss[i+p[i]]和ss[i-p[i]]这里的比较
string ss="$#";
int len=(int)s.length();
for(int i=0;i<len;i++){
ss+=s[i];
ss+="#";
}
len=(int)ss.length();
int r=0;//最右端的值
int mid=0;//中心点
int maxlen=0;//长度
vector<int>p(len,0);
for(int i=1;i<len;i++){
p[i]=r<=i?1:min(p[2*mid-i],r-i);
while(ss[i+p[i]]==ss[i-p[i]]){
p[i]++;
}
if(r<i+p[i]-1){
r=i+p[i]-1;
mid=i;
}
if(maxlen<p[i]){
maxlen=p[i];
}
}
return maxlen-1;
}
