Manacher 算法详解：求解最长回文子串

Manacher（马拉车）算法

问题：

1. 在字符串中，找出所有的回文子串；
2. 在字符串中，找出最长的回文子串； 两个问题可以结合解决。

1.相关概念引入

1.回文字符串： 正着读和反着读都一样的字符串就是回文字符串。 2.回文子串： 一个字符串的某个字串是回文。 3.奇回文串： 回文串的字符数为奇数。 4.偶回文串： 回文串的字符数为偶数。 5.回文中心： c，回文串最中心的位置。奇回文串（回文中心）：n + 1 / 2; 偶回文串（回文中心）：n / 2 与 n/2 + 1 之间 6.回文半径： d，回文中心到回文半径左/右端点的距离（字符数，包括本身）。

2.中心扩展算法

算法原理

1. 从前往后遍历字符串，以 s[i] 或 s[i] 与 s[i + 1] 的中间作为回文串的中心位置；
2. 从中间位置开始，枚举半径长度，逐渐向两边扩展，找出以该点为中心的最长的回文子串。

预处理

为了防止对奇偶回文字串进行分类讨论，且奇回文字串更好处理，这里将其统一转化为奇回文串。 预处理字符串： 在相邻字符之间和整个字符串的两端任意加入一个字符 '#'。 例如，字符串 s = "abcbaa" 经过预处理之后就变成：s = "#a#b#c#b#a#a#"。 经过预处理之后： 本来是奇回文串，处理之后依旧是奇回文串。例如 "bab" 处理后为 "#b#a#b#"； 本来是偶回文串，处理之后就变成奇回文串。例如 "abba" 处理后为 "#a#b#b#a#"； 此时，在处理之后的串上跑中心扩展算法时，由于所有的回文串都是奇回文串，仅需枚举所有中心点，即可找到所有的回文串。

注意： （不用像 kmp 算法那样，加入一个不会出现的字符，这里可以加入任意字符。 因为判断回文的时候，只会原始字符和原始字符判断，新加入的字符和新加入的字符判断。因此，可以加入任意字符。）

代码：

string t, s;
int m, n;
// 以求解最长回文子串为例
int fun(){
    // 预处理字符串
    cin >> t;
    m = t.size();
    s += ' '; // 这里要处理边界不同，' ' != '#'
    for(auto ch : t){
        s += '#';
        s += ch;
    }
    s += "##";
    n = s.size()-2;
    int ret = 1;
    // 中心扩展算法
    for(int i = 1; i <= n; i++){
        int d = 1; // 枚举向右向左的距离
        (s[i - d] == s[i + d]) d++;
        ret = (ret, d - );
    }
     ret;
}