Manacher算法「最长回文字符串」

算法原理

• 最长回文字符串包括奇数长的和偶数长的，求的时候都要分情讨论,Manacher算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘#’字符。
  这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心奇数回文串了。
  其次给每个字符串首部加一个题目中不会出现的字符，避免处理越界问题。（一般加’$’）
  

  
  如图字符串就是通过算法预处理得到的新串
  数组记录的以 为中间字符的回文串向右能匹配的最大长度(包括S[i]这个字符).
  当不是所加字符‘#’时，就是字符串长度了

• 假设以i为中心的回文串长度为,因为]记录以 为中间字符的回文串向右能匹配的长度，所以有
  
  又因为此时串中加了其他字符#，以为中心的回文串一定是以#开头和结尾的，以#为中间字符的就是长度为偶数的，以非#号为中间字符的就是长度为奇数的，例如“#b#b#”或“#b#a#b#”所以减去最前或者最后的‘#’字符就是原串中长度的2倍，即原串长度为，化简的。

算法实现

• 算法实现就是要找出数组,如何找出数组是关键.

首先从左往右依次计算，当计算时，已经计算完毕。设为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为，分两种情况：

情况1：

1. 
   那么找到相对于的对称位置，设为，那么如果
   因为,能向左匹配的最左端点的坐标是
   所以可知,所以可知
   向如下图：
   
   那么说明以为中心的回文串一定在以为中心的回文串的内部，且和关于位置对称,那么意味着以为中间字符的回文串能向右匹配最右端点没有超过。由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，所以。
2. 如果,由对称性，说明以为中心的回文串可能会延伸到之外，而大于的部分我们还没有进行匹配，所以要从位置开始一个一个进行匹配，直到发生失配，从而更新和对应的以及。
   
   虽然p[j]>mx-i,但是可以保证的是这一段是跟是一样的，说明以s[i]为中心的回文串至少有这么长

情况2：

如果i比mx还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新的位置和对应的以及。

        int len=strlen(s);
        int mx=0;
        int id=0;
        int res=-1;
        for(int i=len;i>=0;i--)
        {
            s[i*2+2]=s[i];
            s[i*2+1]='#';
        }
        s[0]='$';//加上特殊字符防止越界
        for(int i=0;i<=2*len+1;i++)
        {
            if(mx>i)//mx<i的情况
            {
                p[i]=min(p[2*id-i],mx-i);//比较p[j]大还是mx-i大，取小的
            }
            else//如果i>=mx，要从头开始匹配
            {
                p[i]=1;
            }
            while(s[i-p[i]]==s[i+p[i]])//一个一个比较
            {
                p[i]++;
            }
            if(p[i]+i>mx))//若新计算的回文串右端点位置大于mx，要更新id和mx的值

            {
                mx=p[i]+i;
                id=i;
            }
            res=max(res,p[i]-1);
        }