题解 | #【模板】马拉车算法#

题目链接

【模板】马拉车算法

题目描述

给定一个长度为 $N$ 的字符串 $S$ ，请求出其最长回文子串的长度。

解题思路

本题是求解最长回文子串的模板题，最高效的算法是 Manacher's Algorithm（马拉车算法），它可以在 $O(N)$ 的线性时间内解决该问题。

1. 预处理字符串

传统求解回文串问题时，需要分别处理长度为奇数和偶数的回文串，比较繁琐。Manacher 算法通过一个巧妙的预处理，将两种情况统一起来。我们在原字符串的每个字符之间以及字符串的两端插入一个特殊的分隔符（如 #）。

例如: aba -> #a#b#a#
例如: abba -> #a#b#b#a#

这样处理后，原字符串中任意长度的回文串，都唯一对应新字符串中一个以某个字符或 # 为中心的、长度为奇数的回文串。

2. 算法核心

算法的核心是计算一个半径数组 $p$ ，其中 $p[i]$ 表示在新字符串中，以第 $i$ 个字符为中心的最长回文子串的半径。

对于新字符串 #a#b#a#$，以 b 为中心的最长回文串是 a#b#a，其半径（不包含中心）为 2。
这个半径值 p[i] 恰好等于其在原字符串中对应的回文子串的长度。

3. 线性时间优化

Manacher 算法通过利用已计算的回文信息来加速后续计算，从而达到线性时间复杂度。

我们维护两个变量 center 和 max_right，表示当前所有已发现的回文子串中，其右边界 (center + p[center]) 到达最远的回文串的中心和它的右边界。
当我们计算 p[i] 时：
- 如果 i 在 max_right 的覆盖范围内 (i < max_right)，我们可以利用 i 关于 center 的对称点 j = 2 * center - i 的信息。由于 i 处的回文串至少在 [center - p[center], max_right] 这个大回文串的范围内是对称的，所以 p[i] 至少为 min(p[j], max_right - i)。我们可以从这个安全的半径开始，再向外进行暴力扩展匹配。
- 如果 i 不在 max_right 的覆盖范围内，我们只能从半径 1 开始暴力扩展。
每次计算完 p[i] 后，如果 i + p[i] 超过了当前的 max_right，我们就更新 center 和 max_right。

通过均摊分析可以证明，max_right 只会单调向右移动，因此总的字符比较次数是线性的。

4. 最终答案

整个 p 数组中的最大值，就是原字符串中最长回文子串的长度。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    // 1. Preprocess the string
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    int m = t.length();

    // 2. Manacher's Algorithm
    vector<int> p(m, 0);
    int center = 0, max_right = 0;
    int max_len = 0;

    for (int i = 0; i < m; i++) {
        // Initialize p[i] using symmetry
        if (i < max_right) {
            p[i] = min(p[2 * center - i], max_right - i);
        }

        // Expand from the initialized radius
        int left = i - (p[i] + 1);
        int right = i + (p[i] + 1);
        while (left >= 0 && right < m && t[left] == t[right]) {
            p[i]++;
            left--;
            right++;
        }

        // Update center and max_right
        if (i + p[i] > max_right) {
            center = i;
            max_right = i + p[i];
        }

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

    cout << max_len << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        // 1. Preprocess the string
        StringBuilder tBuilder = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            tBuilder.append(s.charAt(i));
            tBuilder.append('#');
        }
        String t = tBuilder.toString();
        
        int m = t.length();
        int[] p = new int[m];
        int center = 0, maxRight = 0;
        int maxLen = 0;

        for (int i = 0; i < m; i++) {
            // Initialize p[i] using symmetry
            if (i < maxRight) {
                p[i] = Math.min(p[2 * center - i], maxRight - i);
            }

            // Expand from the initialized radius
            int left = i - (p[i] + 1);
            int right = i + (p[i] + 1);
            while (left >= 0 && right < m && t.charAt(left) == t.charAt(right)) {
                p[i]++;
                left--;
                right++;
            }

            // Update center and maxRight
            if (i + p[i] > maxRight) {
                center = i;
                maxRight = i + p[i];
            }

            // Update maxLen
            maxLen = Math.max(maxLen, p[i]);
        }

        System.out.println(maxLen);
    }
}

def solve():
    s = input()
    
    # 1. Preprocess the string
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    
    p = [0] * n
    center, max_right = 0, 0
    max_len = 0
    
    for i in range(n):
        # Initialize p[i] using symmetry
        if i < max_right:
            p[i] = min(p[2 * center - i], max_right - i)
        
        # Expand from the initialized radius
        left = i - (p[i] + 1)
        right = i + (p[i] + 1)
        while left >= 0 and right < n and t[left] == t[right]:
            p[i] += 1
            left -= 1
            right += 1
            
        # Update center and max_right
        if i + p[i] > max_right:
            center = i
            max_right = i + p[i]
            
        # Update max_len
        max_len = max(max_len, p[i])
        
    print(max_len)

solve()

算法及复杂度

算法：Manacher's Algorithm
时间复杂度： $O(N)$
- 字符串预处理需要 $O(N)$ 。
- 主循环遍历新字符串一次，长度为 $2N+1$ 。虽然内部有 while 循环，但 max_right 指针只会单调向右移动，总移动次数不超过 $2N+1$ 。因此，通过均摊分析，总时间复杂度是线性的。
空间复杂度： $O(N)$
- 需要额外空间存储预处理后的字符串和半径数组 $p$ ，长度均为 $O(N)$ 。