最长回文---Manacher算法解析（俗称：马拉车算法）

题目链接：https://cn.vjudge.net/contest/320014#problem/E

Problem Description
给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input

aaaa
abab 

Sample Output

4
3

分析：

举例：两个字符串：
122122 和bob

1. 对于字符串，长度分奇偶性，对于长度为偶数的，中心点不止一个，所以我们要把字符串全部转化为奇数求解。
2. 字符串每一位都加一位’#’，这样就可以把字符串全部转化为奇数
   原字符串： 122122 和bob
   现字符串#1#2#2#1#2#2# 和#b#o#b#

对于122122 和bob

未加#：（122122）  回文串的长度为5，     加#后（#1#2#2#1#2#2# ），最大回文半径为6
未加#：（bob）     回文串的长度为3，     加#后（#b#o#b# ）        最大回文半径为4

可以得出规律：回文串的最大长度可以通过处理后的字符串的最大回文半径减1求得。

随之产生的问题：若要定位字符串，还需要知道起始位置.

对于122122 和bob：

122122从 i=1的位置产生回文串
bob从    i=0的位置产生回文串

分析：
中间的 ‘1’ 在字符串 #1#2#2#1#2#2# 中的位置是7，而半径是6，貌似 7-6=1，刚好就是回文子串 “22122” 在原串 122122 中的起始位置1。
“bob”，“o” 在 #b#o#b# 中的位置是3，但是半径是4，这一减成负的了，肯定不对。

这就需要对字符串进行二次加工-----思想：把中心位置往后移一位，避免负数的出现----->
我们就需要**在前面增加一个字符，这个字符不能是#号，也不能是s中可能出现的字符，所以我们暂且就用$

引入$后的分析：

“o” 在 $#b#o#b#中的位置是4，半径是4，一减就是0（可以看成：0/2=0）。
‘1’ 在字符串 $#1#2#2#1#2#2# 中的位置是8，而半径是6，这一减就是2了，而原字符串中回文串的起始位置为1，所以我们要除以2。

再来验证一下 “noon”，中间的 ‘#’ 在字符串 $#n#o#o#n# 中的位置是5，半径也是5，相减为0，0/2=0,符合原字符串中回文串的起始位置为0

得出结论：起始位置是中间位置（两次处理后的字符串最大回文串的中心位置）减去半径再除以2
也可以得出现在的字符串长度=原来字符串长度的2倍+2。

1. 定义mp[i]为以i为中心的回文串的半径（mp[i] = 1 代表这个回文串只有自己） ，id 是当前已知最长回文串的中点， mx 是当前已知最长回文串的右端点。

通过上面的分析可以得到mx位置处的字符不属于回文串。（所以下面的更新操作不需要减1）

1. 对于当前位置 i 它的回文半径怎么算呢？

因为我们是顺序遍历的，所以到达 i 之前的所有 mp[ i ]都已经得到了。所有我们可以利用 i ，j 关于id对称的特性来减少“暴力”求解的次数。

核心代码：

p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

当 mx > i 时

①. mx - i > p[ j ] :【mx’,mx】已经是回文串了，也就是说i的左面到id的字符和j的右面到id的字符一样，求p[i]可以转化为求p[j]，此时黄色部分大于j的左面到mx’的距离，也就是 i 的最小半径应该和 j 的半径相等。（mp[ i ] >= Mp[ j ]） 所以最小半径为 p [ j ]
②. mx - i < p[ j ] :黄色部分的长度小于 p [ j ] 那黄色部分，i向右至少会匹配到mx的位置，
最小半径为 mx - i,mx 之后的部分是否对称，就只能老老实实去匹配了，这就是后面紧跟到 while 循环的作用。

当mx<=i时，无法找到对称点快速求解，此时将p[i]=1,执行while循环，往两边扩，若a[i+p[i]]==a[i-p[i]] 相等，p[i]++。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 110002
char ch[N],a[N<<1];
int p[N<<1];
void manacher(int len)
{
    int l=0;
    a[l++]='$';
    a[l++]='#';
    for(int i=0; i<len; i++)
    {
        a[l++]=ch[i];
        a[l++]='#';
    }
    int mx=0,id=0;
    for(int i=0; i<l; i++)
    {
        p[i]=mx>i?min(mx-i,p[2*id-i]):1;
        while(a[i+p[i]]==a[i-p[i]])p[i]++;
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
    }
}
int main()
{
    while(~scanf("%s",ch))
    {
        int len=strlen(ch);
        manacher(len);
        int res=0;
        for(int i=0; i<2*len+2; i++)
            res=max(res,p[i]-1);
        printf("%d\n",res);
    }
    return 0;
}