如何找到时间复杂度最优的最长回文子串？

示例1 #

Input: s = "babad"
Output: "bab"
Explanation: "aba" 也是有效答案。

我目前的解法速度太慢，代码如下：

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0)
        return s;
    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i++) {
        if(s.length()-i < longest.length()/2)
            break;
        String oddPal = findLengthofPalindrome(s, i, i);
        if (longest.length() < oddPal.length()) {
            longest = oddPal;
        }

        String evenPal = findLengthofPalindrome(s, i, i + 1);
        if (longest.length() < evenPal.length()) {
            longest = evenPal;
        }
    }
    return longest;

}

private String findLengthofPalindrome(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return s.substring(left + 1, right);
}

你的解法采用的是中心扩展法，时间复杂度为O(n²)，对于较长字符串会存在性能瓶颈。时间复杂度最优的解法是Manacher算法，可将时间复杂度降至O(n)。

Manacher算法核心思路 #

1. 预处理字符串：在每个字符间插入特殊符号（如#），统一奇偶长度回文的处理逻辑（例如babad变为#b#a#b#a#d#）。
2. 维护三个关键变量：
   • center：当前已知最长回文子串的中心位置
   • right：当前已知最长回文子串的右边界
   • p[]：数组，p[i]表示以i为中心的最长回文子串半径（对应原字符串的实际长度为p[i]）
3. 利用已计算的回文信息避免重复扩展：当遍历到位置i时，若i在right范围内，可通过对称位置mirror = 2*center - i的p[mirror]值初始化p[i]，再进行扩展，减少重复计算。

实现代码 #

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) return "";
    
    // 预处理字符串，统一奇偶回文处理
    StringBuilder sb = new StringBuilder();
    sb.append('#');
    for (char c : s.toCharArray()) {
        sb.append(c).append('#');
    }
    String processed = sb.toString();
    int n = processed.length();
    
    int[] p = new int[n];
    int center = 0, right = 0;
    int maxLen = 0, startIdx = 0;
    
    for (int i = 0; i < n; i++) {
        // 利用对称位置初始化p[i]
        if (i < right) {
            int mirror = 2 * center - i;
            p[i] = Math.min(right - i, p[mirror]);
        }
        
        // 尝试扩展回文
        int left = i - (p[i] + 1);
        int rightNew = i + (p[i] + 1);
        while (left >= 0 && rightNew < n && processed.charAt(left) == processed.charAt(rightNew)) {
            p[i]++;
            left--;
            rightNew++;
        }
        
        // 更新center和right
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        // 更新最长回文子串信息
        if (p[i] > maxLen) {
            maxLen = p[i];
            startIdx = (i - maxLen) / 2; // 转换回原字符串的起始索引
        }
    }
    
    return s.substring(startIdx, startIdx + maxLen);
}

复杂度分析 #

• 时间复杂度：O(n)，每个字符最多被访问两次（扩展过程不会重复处理已覆盖区域）。
• 空间复杂度：O(n)，用于存储预处理后的字符串和p数组。

内容的提问来源于stack exchange，提问作者Markov_Fedor