# Manacher 算法

# 背景

给定一个字符串，求出其最长回文子串。例如：

1. s="abcd"，最长回文长度为 1；
2. s="ababa"，最长回文长度为 5；
3. s="abccb"，最长回文长度为 4，即 bccb。

以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为 O (n2)，效率很差。

1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到 O (n)。下面来看看马拉车算法是如何工作的。

# 算法分析

因为回文字符串分为偶回文和奇回文字符串而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：

1. 在字符串首尾及每个字符间都插入一个 "#"，这样可以使得原先的奇偶回文都变为奇回文；

2. 接着再在首尾两端各插入 "$" 和 "^"，这样中心扩展寻找回文的时候会自动退出循环，不需每次判断是否越界，可参见下面代码。

3. 上述新插入的三个字符，即 "#"、 "$" 和 "^"，必须各异，且不可以与原字符串中的字符相同。

   例如： s="abbahopxpo" ，转换为 s_new="$#a#b#b#a#h#o#p#x#p#o#^" 。如此，s 里起初有一个偶回文 abba 和一个奇回文 opxpo ，被转换为 #a#b#b#a# 和 #o#p#x#p#o# ，长度都转换成了奇数。

   定义一个辅助数组 int p[] ，其中 p[i] 表示以 i 为中心的最长回文的半径，例如：

   可以知道 p [i]-1 就是最终的回文长度。然后 i 是当前回文字符串，mx 是当前 i 回文右移最大位置，2*id-i 是当前 i 以 id 为对称点的左边位置

   if(i<mx)
   {
   	p[i]=min(p[2*id-i],mx-i)
   }
   

如果当前 i 小于等于右边最大位置的回文字符 mx，那么则依次填入 p [i] 当中，以当前字符为中心的最大回文数。

再以当前确定的回文数，继续依次向两边进行比较是否相等，如果想到，那么就在原有基础之上继续自增，直到退出循环，p [i] 的值就是第 i 各字符的最大回文数。

while(p[i-p[i]]==p[i+p[i]])
p[i]++;

最后只需依次更新最大回文数 max_len 即可，p [i]-1 就是当前的回文数。

max_len = max(max_len, p[i] - 1);

如果需要最大回文字符串，那么只需要使用如此代码

  if((p[i]-1)>max_len)
        {
            max_len=p[i]-1;
            start=(id-max_len)/2;
        }

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string.h>

using namespace std;

string s;
char s_new[2000];
int p[2000];
int start;
int max_len = -1;  // 最长回文长度

int Init()
{
    int len = s.size();
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j++] = '^'; 
    s_new[j] = '\0';  

    return j;  // 返回 s_new 的长度
}

string Manacher()
{
    int len = Init();  // 取得新字符串长度并完成向 s_new 的转换


    int id;
    int mx = 0;

    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i); 
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断，因为左有 $，右有 ^
            p[i]++;
        
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }
        if((p[i]-1)>max_len)
        {
            max_len=p[i]-1;
            start=(id-max_len)/2;
        }

        //max_len = max(max_len, p[i] - 1);
    }

    return s.substr(start,max_len);
}

int main()
{

        cin>>s;
        cout<<Manacher()<<endl;
        cout<<max_len<<endl;
    return 0;
}