小学生都能看懂的题解 | #最长回文子串#

要计算字符串中最长回文子串的长度，我们可以使用一种有效的算法，称为“中心扩展法”，并将其优化为 Manacher 算法，满足 O(n) 的时间复杂度和 O(n) 的空间复杂度。以下是这一方法的详细解释和 Java 代码实现。

什么是回文子串？

回文子串是指从前往后读和从后往前读都相同的字符串。例如：

• "aba" 和 "abba" 都是回文子串。
• "abc" 不是回文子串。

解决方案：Manacher 算法

Manacher 算法是解决最长回文子串问题的一种高效算法，具有 O(n) 的时间复杂度。其主要思想是利用已经计算出的回文信息，避免重复的计算，从而提高效率。

算法步骤

1. 预处理字符串：为了处理偶数长度的回文，我们在每个字符之间插入一个特殊字符（如 #），并在字符串的开头和结尾加上一个特殊字符（如 $）。例如，将 "ababc" 转换为 "$#a#b#a#b#c#$"。

2. 维护一个数组：使用一个数组 P 来记录每个中心扩展的回文半径。P[i] 表示以字符 i 为中心的回文半径。

3. 使用中心和右边界：维护一个变量 C 来表示当前已知的回文中心，R 表示这个回文的右边界。对于每个新字符 i，如果 i 在 R 右边，就从 C 开始扩展；否则，直接利用对称性来获取初始的回文半径。

4. 扩展回文：尝试从 i 向外扩展，直到不满足回文的条件，更新 P[i] 的值。

5. 更新最长回文长度：在遍历的过程中，记录最大回文半径，转换为回文长度。

Java 代码实现

下面是 Manacher 算法的 Java 实现代码：

public class LongestPalindromeSubstring {

    public static int longestPalindromeLength(String s) {
        if (s == null || s.length() == 0) {
            return 0; // 如果字符串为空，返回0
        }

        // Step 1: 预处理字符串
        StringBuilder processedString = new StringBuilder();
        processedString.append('$'); // 添加开始标记
        processedString.append('#'); // 添加间隔标记

        for (char c : s.toCharArray()) {
            processedString.append(c);
            processedString.append('#'); // 在每个字符后面添加间隔标记
        }
        processedString.append('!'); // 添加结束标记

        // Step 2: Manacher算法初始化
        int n = processedString.length();
        int[] P = new int[n]; // P[i] 表示以 i 为中心的回文半径
        int C = 0; // 当前回文中心
        int R = 0; // 当前回文右边界

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * C - i; // 计算当前字符的对称位置

            // 如果 i 在 R 的左边，利用之前的计算值
            if (R > i) {
                P[i] = Math.min(R - i, P[mirror]);
            }

            // Step 3: 扩展回文
            while (processedString.charAt(i + P[i] + 1) == processedString.charAt(i - P[i] - 1)) {
                P[i]++;
            }

            // 更新中心和右边界
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        // Step 4: 找到最长的回文长度
        int maxLength = 0;
        for (int length : P) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength; // 返回最长回文子串的长度
    }

    public static void main(String[] args) {
        String s1 = "ababc";
        String s2 = "abbba";
        String s3 = "b";

        System.out.println(longestPalindromeLength(s1)); // 输出: 3
        System.out.println(longestPalindromeLength(s2)); // 输出: 5
        System.out.println(longestPalindromeLength(s3)); // 输出: 1
    }
}

代码说明

• 预处理字符串：在原字符串中添加特殊字符，方便处理奇数和偶数长度的回文。
• 初始化变量：P 数组记录回文半径，C 和 R 分别表示当前中心和右边界。
• 计算回文半径：通过对称性和扩展来计算每个位置的回文半径。
• 更新最大长度：遍历 P 数组，找到最大回文半径的值。

希望这篇文章对你有帮助👍。