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() - ;
     ret = ;
    
     ( i = ; i <= n; i++) {
         d = ;
        
         (s[i - d] == s[i + d]) d++;
        ret = (ret, d - );
    }
     ret;
}