Manacher 算法 ，用以求解最长回文字符串，其时间复杂度为o（n）,

这个算法首先最帅的一点在于对奇偶字符串的处理，例如aba和abba，那么仅仅需要在每个字符之间（包括外层）插入一个原字符串没有的字符，一般用“#”或者“$”，此时aba变成了：

#a#b#a# 仍是以b为中心的奇数长度回文字符串

此时abba变成了：

#a#b#b#a#这是其变成了以“#”为中心的奇数长度回文字符串

有了以上的处理就可以将奇偶字符串统一拓展为奇数长度字符串进行处理。

但是manacher 算法中对字符串的处理还要进行防止越界处理（具体原因见下文处理）

比如对abba字符串的处理（注意下标）

a b b a 其下标为：

0 1 2 3预处理后的字符串

@#a#b#b#a#$ 其下标为

0 1 23456789 10

1.我们处理过的要用的字符串从下标从1 开始

2.为防止越界要在新字符串下标为0的位置 和字符串的末尾添加两个原来串没有又不同的字符

我这里用的就是@ 和 $

下面贴预处理的代码

void pre_change()
{
    newstr[0] = '@' ; 
    newstr[1] = '#' ; 
    for(int i = 0 ; i < len ; i ++ )
    {
        newstr[2*i + 2 ] = str[i] ; 
        newstr[2*i + 3 ] = '#' ; 
    }
    newstr[2 * len + 2 ] = '$' ; 
    return ; 
}

这样就预处理完毕了，接下来是该最精彩的部分 ；

用一个数组 r [i] 记录 以newstr[i]为中心的最长回文串的半径长度

r[i]数组是马拉车算法的核心！！！！

用 maxid 记录 在位置 i 以前的回文串右边能延伸到的最大位置

即maxid = id + r[id] ;

id 即对应maxid

注意这个id 不是 i 而是之前某个位置的下标 ！

然后就用了动态规划的思想以o（n）的复杂度更新了所有的newstr[i] 对应的r[i] ;

接下来先看代码!

void Manacher()
{
   int id , maxid = 0 ; 
   len = 2 * len + 2 ； 
   for(int i = 0 ; i < len ; i ++ )
   {
   if(maxid > i )
   r[i] = min(r[2 * id - i] , maxid - i ) ; 
   else r[i] = 1 ; 
   
   while(newstr[i + r[i]] == newstr[i - r[i]])
         r[i] ++ ; 
   if( r[i] + i > maxid)
   {
       maxid = r[i] + i ;
       id = i ; 
   }
   }
}

先看看动态规划更新r[i]的核心部分

for(int i = 0 ; i < len ; i ++ )
   {
   if(maxid > i )
   r[i] = min(r[2 * id - i] , maxid - i ) ; 
   else r[i] = 1 ; 

如上图由 已知可以知道 j = 6 , i = 14 , maxid = mi = 17 , id = 10 ;

可以明显看出r[i] = 4 ，即11到i

r[j] = 6 ; 即j 到11

j 是i 关于id对称位置的下标

并且有j = 2 * id - i ;

根据对称原理可知

若newstr[j]处有回文串 ， 则其对称位置newstr[i]处最大回文串半径r[i] = r[j] ;

如上图这里j处对称过来的回文串长度 加上i的坐标显然超过了mi 即 maxid ，这时r[i]只需要取mi - i 即可

即有状态转移方程 r[i] = min(r[j] , maxid - i) ;

即上面核心代码maxid > i的部分

若maxid < i，很显然在 i 并不在回文串id -maxid 到id + maxid内，此时newstr[i]只能跟自己构成回文串了，故r[i] = 1 ; 然后是

  while(newstr[i + r[i]] == newstr[i - r[i]])
         r[i] ++ ; 

直接更新位置i处的回文串半径，不再赘述。

最后有

 while(newstr[i + r[i]] == newstr[i - r[i]])
         r[i] ++ ; 
   if( r[i] + i > maxid)
   {
       maxid = r[i] + i ;
       id = i ; 
   }

如上文所述 maxid为i前回文串向后延伸的最远位置 ，若i处向后延伸的回文串还能更远，那么更新

maxid ，这时候id 就更新为 i 。

经过如上面的一轮循环，我们就找到了字符串中关于每个位置i的最大回文串半径r[i] ！！！！

设L[i]为x新字符串中以newstr[i]为中心的最长回文串长度

那么显然有 L[i] = 2 * r[i] - 1

容易知道 L[i]的长度总为奇数字符串的长度

对于两种字符串 #a#b#a#或#a#a#

其对应的回文串长度（L -1）/2 即为原来的字符串长度！

该值为r[i] - 1 ！！！

那么想要找到这一个字符串中最长的回文串的长度，不断更新r[i] - 1的最大值即可！！

于是用来求最长回文串长度的代码如下

void Manacher()
{  int max_len = 0 ; 
   int id , maxid = 0 ; 
   len = 2 * len + 2 ； 
   for(int i = 0 ; i < len ; i ++ )
   {
   if(maxid > i )
   r[i] = min(r[2 * id - i] , maxid - i ) ; 
   else r[i] = 1 ; 
   while(newstr[i + r[i]] == newstr[i - r[i]])
         r[i] ++ ; 
   if( r[i] + i > maxid)
   {
       maxid = r[i] + i ;
       id = i ; 
   } max_len = max(max_len,r[i] - 1 );
   }
 
      
 printf("%d\n",max_len) ; 
    
}

以上就是马拉车算法的教程，有一说一马老先生是真的NB！

马拉车算法用于解决回文串问题，个人经常会忘记其原理，所以在此整理一下。
对于回文串，简单说即正着念和反着念是一样的字符串，如abba。用常规的暴力方法，即以一个字符为中心，两边分别外扩，比较每个字符。这种方法需要分奇偶来讨论，即如aba和abba这两种情况。
1.马拉车算法首先需要对字符串进行处理，在字符串开头结尾及字符间穿插同一个特殊字符，该字符可以是任何字符，不影响结果。
处理后的字符串，不管原字符串长度是奇是偶，都变成了奇，这样就可以以同一种方式处理了。
2.这里引入两个变量，分别是R和C。下面将解释两个变量的意义。
假设下图方框表示以a为中心的回文字符串

我们用一个数组array来表示对以应位置的字符为中心，其最长的回文字符串长度。即array[7] = 8。那么我们知道，在以a为中心的回文字符串中，因为对称的关系，左右两边有着相同的子串

依照这个特性，后面字符的array值，是可以参考前面对称位置字符的array值的。R的作用是框定当前回文半径最长的距离（只增不减），即上图14的位置，而c则是以R为半径的回文串中心。这里分两种情况。
（1）若当前i的位置小于R（即如上图在红框内），则以其对称位置2c-i的array值为基础，再向外扩展。
（2）若i大于R，即在红框外，array初始值设为1，则需要按照之前的方式，两边展开来比较，无优化。比较完后再更新R和C值。

//预先处理字符串
string getmancher(string str)
{
    string res(2*str.length()+1,0);
    int j = 0;
    for(size_t i = 0;i<str.length();i++)
    {
        res[j] = '#';
        res[j+1] = str[i];
        j = j+2;
    }
    res[2*str.length()]= '#';
    return res;
}

int maxbackstr(string str)
{
    int Max = INT32_MIN;
    int R = -1;
    int C = -1;
    int array[str.length()];
    for(int i = 0;i<str.length();i++)
    {
            array[i] = i>=R?1:min(array[2*C-i],R-i-1);
            while(i+array[i]>=0 && i+array[i]<str.length()){
                if(str[i-array[i]] == str[i+array[i]])
                    array[i]++;
                else
                    break;
            }
            if(R<i+array[i]-1){
            R = i+array[i]-1;
            C = i;
            }
            Max = max(Max,array[i]);
     }
            return Max-1;
}

int main()
{
    string str = "abba";
    cout<<maxbackstr(getmancher(str))<<endl;
    return 0;
}

对字符串要进行遍历，由于R不会回退，故时间复杂度为O（n）。