Manacher 算法简介

doMore 250 2024-10-11

简介

Manacher 算法是一种用于在线性时间内找到字符串中最长回文子串的算法。该算法的核心思想是利用回文的对称性,通过动态规划的方式避免重复计算,从而显著提高效率。下面我将详细解释这个算法,并给出一个 Java 示例。

算法详解

1. 预处理字符串

为了处理奇数长度和偶数长度的回文子串,Manacher 算法通过在每个字符之间(包括字符串首尾)插入一个特殊字符(如 #),并在字符串首尾添加不同的特殊字符(如 ^ 和 $),从而将所有情况统一为奇数长度处理。

注意: 特殊字符 ^ 和 $ 也可以不加,算法需要特殊处理一下

2. 定义辅助数组

  • 定义一个数组 p,其中 p[i] 表示 以 i 为中心的最长回文子串的半径(包括中心字符)
  • 半径的定义使算法可以方便地利用回文的对称性

3.初始化

  • 初始化 p 数组,并设置两个指针 c (当前回文中心) 和 r (当前回文边界)

4. 遍历字符串

  • 对于每个字符 i,计算其对应的回文半径 P[i]
  • 如果 i 在 R 的左边(即 i < R),则利用对称性找到 i 关于 C 的对称点 j = 2*C - i
    • 如果 P[j] 不超过 R - i(即对称的回文部分完全在已知的回文内部),则 P[i] = P[j]
    • 否则,需要扩展 i 的回文半径,直到遇到不匹配的字符或到达字符串边界。
  • 更新 C 和 R,如果 i + P[i] > R,则更新 C = i 和 R = i + P[i]

5. 找到最长的回文子串

  • 遍历 P 数组,找到最大的 P[i],其对应的回文子串即为原字符串中从 i - P[i] / 2 到 i + P[i] / 2 - 1(去除预处理字符)的子串。
// 此处算法中没有 在开头结尾添加特殊字符。只用到分隔符 "#"

public class L5 {  
  
    public static void main(String[] args) {  
        L5 l5 = new L5();  
        String r = "babad";  
        String s = l5.longestPalindrome(r);  
        System.out.println(s);  
    }  
  
  public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        char[] str = marcherString(s);

        int[] p = new int[str.length];
        marcherFind(str, p, 0);
        
        // 找到最长回文子串
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < p.length - 1; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }

        // 提取原字符串中的最长回文子串
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    private void marcherFind(char[] s, int[] p, int l) {
        int c = l - 1;
        int r = l - 1;
        int n = s.length;
        for (int i = l; i < n; i++) {
            p[i] = r > i ? Math.min(p[2 * c - i], r - i) : 1;
            while (i + p[i] < n && i - p[i] > l - 1 && s[i + p[i]] == s[i - p[i]]) {
                p[i]++;
            }
            p[i]--;
            if (i + p[i] > r) {
                r = i + p[i];
                c = i;
            }
        }
    }

    private char[] marcherString(String s) {
        char[] chars = s.toCharArray();
        char[] ans = new char[chars.length * 2 + 1];
        int index = 0;
        for (int i = 0; i != ans.length; i++) {
            ans[i] = (i & 1) == 0 ? '#' : chars[index++];
        }
        return ans;
    }
}