Java实现Manacher最长回文子串算法

简介

在字符串处理中，寻找最长回文子串是一个经典的问题。Manacher算法是一种高效解决此问题的算法，它的时间复杂度为 O(n)，其中 n 是字符串的长度。相比暴力解法的 O(n^2) 复杂度，Manacher算法极大地提高了效率。本文将详细介绍Manacher算法在Java中的实现，包括基础概念、使用方法、常见实践以及最佳实践。

基础概念

回文子串

回文子串是字符串中一个连续的子序列，该子序列从左到右和从右到左读起来是一样的。例如，在字符串 “abba” 中，“abba” 本身以及 “bb” 都是回文子串。

Manacher算法原理

Manacher算法的核心思想是通过利用已经计算出的回文子串信息，避免重复计算，从而实现线性时间复杂度。

预处理字符串：为了统一处理奇数长度和偶数长度的回文子串，Manacher算法首先对原字符串进行预处理，在每个字符的两边插入一个特殊字符（通常是 ’#’）。例如，字符串 “aba” 预处理后变为 “#a#b#a#“。这样处理后，所有回文子串的长度都变为奇数。
利用回文对称性：算法使用一个数组 p[] 来记录以每个字符为中心的回文子串的半径。对于一个已知的回文子串，其左右两边是对称的。利用这种对称性，可以快速计算出部分位置的回文半径。
中心扩展：在计算每个位置的回文半径时，先利用对称性获取一个初始值，然后通过中心扩展的方式来验证并更新回文半径。

Java实现

代码示例

public class Manacher {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        // 预处理字符串
        StringBuilder t = new StringBuilder("#");
        for (char c : s.toCharArray()) {
            t.append(c).append("#");
        }
        
        int[] p = new int[t.length()];
        int center = 0, right = 0;
        int maxLen = 0, maxCenter = 0;
        
        for (int i = 0; i < t.length(); i++) {
            int mirror = 2 * center - i;
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            } else {
                p[i] = 1;
            }
            
            // 中心扩展
            while (i - p[i] >= 0 && i + p[i] < t.length() && t.charAt(i - p[i]) == t.charAt(i + p[i])) {
                p[i]++;
            }
            
            // 更新中心和右边界
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            
            // 更新最长回文子串的长度和中心位置
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }
        
        // 计算最长回文子串在原字符串中的起始和结束位置
        int start = (maxCenter - maxLen + 1) / 2;
        int end = start + maxLen - 2;
        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println("最长回文子串: " + longestPalindrome(s));
    }
}

代码解析

预处理字符串：通过 StringBuilder 将原字符串处理为以 ’#’ 分隔的新字符串，方便统一处理奇数和偶数长度的回文子串。
初始化变量：p[] 数组用于存储每个位置的回文半径，center 表示当前已知的最右回文子串的中心，right 表示其右边界。
遍历字符串：在遍历过程中，利用回文的对称性初始化 p[i]，然后通过中心扩展来更新 p[i]。
更新中心和右边界：如果当前回文子串的右边界超过了已知的最右回文子串的右边界，则更新 center 和 right。
计算最长回文子串：根据 maxLen 和 maxCenter 计算出最长回文子串在原字符串中的位置，并返回结果。

使用方法

输入与输出

输入：longestPalindrome 方法接受一个字符串作为输入参数。
输出：返回输入字符串中的最长回文子串。

调用示例

public class Main {
    public static void main(String[] args) {
        String s = "cbbd";
        String result = Manacher.longestPalindrome(s);
        System.out.println("最长回文子串: " + result);
    }
}

常见实践

应用场景

文本处理：在自然语言处理中，检测句子中的回文结构，例如判断诗词中的回文句。
密码学：某些密码算法可能会利用回文特性进行加密或解密。
数据验证：验证输入字符串是否包含特定的回文模式。

性能优化

减少内存开销：在预处理字符串时，可以直接在原字符串上进行操作，避免额外的字符串创建。
并行处理：对于非常长的字符串，可以考虑使用并行计算来加速中心扩展的过程。

最佳实践

代码优化

边界检查：在方法开始时，对输入字符串进行边界检查，如为空或长度为 0 的情况，直接返回空字符串，提高代码的健壮性。
简化逻辑：尽量简化中心扩展的逻辑，减少不必要的条件判断，提高代码的可读性和执行效率。

错误处理

异常处理：在可能出现异常的地方，如字符串操作，添加适当的异常处理，确保程序在遇到错误时能够优雅地处理。
输入验证：在调用 longestPalindrome 方法前，对输入字符串进行验证，确保输入符合预期。

小结

本文详细介绍了Manacher算法在Java中的实现，包括基础概念、代码实现、使用方法、常见实践以及最佳实践。通过Manacher算法，可以高效地找到字符串中的最长回文子串，在各种字符串处理场景中具有重要的应用价值。希望读者通过本文的学习，能够深入理解并灵活运用该算法。