简介

Manacher 算法是一种高效的算法，用于在O(n)时间求解出字符串的回文半径数组。回文半径数组即以当前字符为中心的最长回文半径，利用回文半径数组可以进一步求解最长回文子串等问题。它的核心思想是利用回文的对称性和已计算出的回文半径，避免重复计算。

算法步骤

  1. 预处理字符串：回文串长度可能为奇数或偶数，为了简化边界处理，将原字符串转换为一个新字符串，每个字符之间插入一个特殊字符（如 #），例如 "abc" 转换为 "#a#b#c#"。
  2. 初始化数组：定义一个数组 radius，用于存储每个位置的回文半径。
  3. 中心扩展：从每个字符出发，向两边扩展，找到以该字符为中心的最长回文子串。
  4. 利用已知信息：通过已计算的回文半径，避免重复计算。

避免重复计算的机制

核心概念

Manacher 算法通过以下两个关键变量来避免重复计算：

  1. R（最右边界）：当前已知的最右边界，即所有已计算的回文子串中，最右边的字符位置。
  2. C（中心位置）：与 R 对应的回文子串的中心位置。

这两个变量帮助我们利用已知的回文信息，从而跳过不必要的计算。

如何利用已计算的回文半径

假设我们已经计算了字符串中部分位置的回文半径，并且维护了当前的 R 和 C。当我们计算新位置 i 的回文半径时，会有以下两种情况：

1. 当前位置 i 在已知的最右边界 R 内部

如果 i 在 R 内部，即 i < R，那么位置 i 的回文半径可以通过已知的回文半径来快速确定。

具体来说：

  • 位置 i 关于中心 C 的对称位置是 2*C - i。

  • 如果 i 的对称位置 2*C - i 的回文半径小于或等于 R - i，那么位置 i 的回文半径可以直接继承对称位置的回文半径：

    1
    radius[i] = radius[2*C - i];

  • 如果 i 的对称位置的回文半径大于 R - i，那么位置 i 的回文半径最多只能扩展到 R - i：

    1
    radius[i] = R - i;

2. 当前位置 i 在已知的最右边界 R 外部

如果 i 在 R 外部，即 i >= R，那么我们无法利用已知的回文信息，必须从头开始计算位置 i 的回文半径：

1
radius[i] = 1;  // 初始化为1，表示至少包含自身

然后通过中心扩展法逐步扩展：

1
2
3
while (i - radius[i] >= 0 && i + radius[i] < n && s.charAt(i - radius[i]) == s.charAt(i + radius[i])) {
    radius[i]++;
}

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public String plus(String s){
    StringBuilder sb = new StringBuilder();
    sb.append('#');
    for(int i = 0;i < s.length();++i){
        sb.append(s.charAt(i));
        sb.append('#');
    }
    return sb.toString();
}

public int getRadius(String s) {
    s = plus(s);
    int n = s.length();
    int[] radius = new int[n];
    int R = 0, C = -1;
    for(int i = 0;i < n;++i){
        radius[i] = i >= R ? 1 : Math.min(radius[2*C - i], R - i);
        while(i - radius[i] >= 0 && i + radius[i] < n){
            if(s.charAt(i-radius[i]) == s.charAt(i+radius[i])) ++radius[i];
            else break;
        }
        if(i + radius[i] > R){
            R = i + radius[i];
            C = i;
        }
    }
    return radius;
}

__END__