马拉车算法（Manacher’s algorithm）—— 线性时间查找最长回文子串

^{图片来源：Easy Diffusion 生成（参数）， Aseprite 编辑}

回文字符串

简单来说就是左右对称的字符串，比如 aba、abba 都是回文字符串。

寻找最长回文子串是很经典的问题，比如 bananas 的最长回文子串就是 anana （LeetCode 上对应的题目 longest-palindromic-substring）

暴力计算（O(n²)）

一个简单的想法是，对于字符串里的一个字符 c：

1. 我们尝试把该字符作为中心，逐次比较 c 两边的字符是否相同，这样就得到以 c 为中心时的最长回文字符串
2. 对每一个字符都重复 步骤 1 ，这样就得到了所有位置的最长回文字符串，把他们保存下来，比较长度即可找到最长回文子串

显然上面的想法会漏掉偶数长度的回文串（比如 cabba ，无论以哪个字符为中心开始找都得不到 abba），我们可以通过插入额外字符来把所有偶数长度的回文串转化为奇数长度，比如我们插入字符 | ，把 cabba 转化为 |c|a|b|b|a|

马拉车算法（O(n)）

马拉车算法其实上面的想法差不多，也是尝试以每一个字符为中心查找局部的最长回文串，不同的是马拉车算法利用来回文串左右对称的特点减少来大量计算

rust 实现的样例代码
pub fn longest_palindrome(s: String) -> String {
    // 在每个字符之间插入字符'|'，包括开头和结尾
    let mut p = s.chars().fold(Vec::new(), |mut acc, c| {
        acc.push('|');
        acc.push(c);
        acc
    });
    p.push('|');

    let lenght = p.len();
    // radii[i] 表示以 p[i] 为中心的最大回文半径，通过回文中心和半径可以确定一个回文字符串
    let mut radii = vec![0; lenght];
    let mut i = 0;
    while i < lenght {
        // 对于情况3, 在上一次循环中已经确定了最小回文半径，不必从0开始
        let mut radius = radii[i];

        // 比较 p[i] 两边的字符，确定以 p[i] 为中心的最大回文半径
        while i > radius
            && i + radius + 1 < lenght
            && p[i - (radius + 1)] == p[i + (radius + 1)]
        {
            radius += 1;
        }

        radii[i] = radius;

        // 利用回文的对称性，直接得到 p[i+1] 到 p[i + radius] 的最大回文半径
        let mut j = 1;
        while j <= radius {
            let right = i + j;
            let left = i - j;
            let left_radius = radii[left];

            if left_radius < radius - j {
                // 情况1
                radii[right] = left_radius;
            } else if left_radius > radius - j {
                // 情况2
                radii[right] = radius - j;
            } else { // left_radius == radius - j
                // 情况3
                // 以 radii[right]为中心的回文半径至少为 radius - j，下次循环会尝试继续向右扩展
                radii[right] = radius - j;
                break;
            }
            j += 1;
        }

        i += j;
    }

    // 找到最大回文串的中心和半径
    let (i, r) = radii
        .iter()
        .enumerate()
        .max_by_key(|(_, &value)| value)
        .unwrap();

    // 去掉插入的字符'|'
    p[(i - r)..=(i + r)]
        .iter()
        .filter(|c| c != &&'|')
        .collect::<String>()
}

---

参考：

• 最长回文字串——维基百科

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。