解题思路

这是一个寻找最长回文子串的问题。提供两种解法：朴素解法和Manacher算法。

朴素解法详解

  1. 中心扩展思想：

    • 遍历字符串的每个位置作为可能的回文中心
    • 对每个中心，分别考虑奇数长度和偶数长度的情况
    • 向两边扩展，直到不满足回文条件为止

  2. 处理两种情况：

    • 奇数长度：以当前字符为中心，如"aba"中的'b'
    • 偶数长度：以当前字符和下一个字符之间为中心，如"abba"中的"bb"之间

  3. 实现细节：

    • 使用双指针 向两边扩展
    • 每次扩展都更新最大长度
    • 注意边界条件的处理

Manacher算法详解

  1. 预处理字符串：

    • 在原字符串的每个字符间插入特殊字符（通常用'#'）
    • 在首尾添加不同的特殊字符（如'$'和'@'），避免边界判断
    • 例如："abba" -> "$#a#b#b#a#@"

  2. 核心概念：

    • ：以位置 为中心的回文半径
    • ：当前最大回文串的中心位置
    • ：当前最大回文串的右边界

  3. 算法步骤：

    • 遍历预处理后的字符串
    • 利用已知回文信息快速跳过一些计算
    • 使用中心扩展法尽可能扩大回文半径
    • 更新 和
    • 维护最大回文半径

  4. 优化原理：

    • 利用回文串的对称性
    • 已计算的回文信息可以帮助计算新的位置
    • 通过right边界减少不必要的比较

示例分析

以输入 "cdabbacc" 为例：

  1. 朴素解法过程：

    • 遍历每个字符作为中心点
    • 找到 "abba" 是最长的回文子串
    • 长度为4

  2. Manacher算法过程：

    • 预处理后：$#c#d#a#b#b#a#c#c#@
    • 计算每个位置的回文半径
    • 最大回文半径对应原始字符串中的最长回文子串

算法选择建议

  1. 朴素解法：

    • 优点：实现简单，容易理解
    • 缺点：时间复杂度较高
    • 适用：字符串长度较小（如本题≤350）的情况

  2. Manacher算法：

    • 优点：线性时间复杂度，处理大规模数据高效
    • 缺点：实现复杂，需要预处理
    • 适用：字符串长度很大或需要高性能的场景

复杂度分析

  1. 朴素解法：

    • 时间复杂度：
      • 遍历每个中心点：
      • 每个中心点向两边扩展：
    • 空间复杂度：
      • 只需要常量额外空间

  2. Manacher算法：

    • 时间复杂度：
      • 虽然有两层循环，但内层循环的总执行次数是有限的
      • 每个位置最多被访问常数次
    • 空间复杂度：
      • 需要存储预处理后的字符串
      • 需要 数组存储回文半径

代码

C++实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 朴素解法
class Solution1 {
public:
    int longestPalindrome(string s) {
        int maxLen = 1;
        int n = s.length();
        
        for(int i = 0; i < n; i++) {
            // 奇数长度
            int l = i, r = i;
            while(l >= 0 && r < n && s[l] == s[r]) {
                maxLen = max(maxLen, r - l + 1);
                l--; r++;
            }
            
            // 偶数长度
            l = i; r = i + 1;
            while(l >= 0 && r < n && s[l] == s[r]) {
                maxLen = max(maxLen, r - l + 1);
                l--; r++;
            }
        }
        return maxLen;
    }
};

// Manacher算法
class Solution2 {
public:
    int longestPalindrome(string s) {
        string t = "$#";
        for(char c : s) t += c, t += "#";
        t += "@";
        
        int n = t.size();
        vector<int> p(n, 0);
        int maxLen = 0;
        int center = 0, right = 0;
        
        for(int i = 1; i < n-1; i++) {
            if(i < right) p[i] = min(right - i, p[2 * center - i]);
            
            while(t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
            
            if(i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            maxLen = max(maxLen, p[i]);
        }
        return maxLen;
    }
};

int main() {
    string s;
    cin >> s;
    Solution1 sol1;
    // Solution2 sol2;
    cout << sol1.longestPalindrome(s) << endl;
    return 0;
}

import java.util.*;

public class Main {
    // 朴素解法
    static class Solution1 {
        public int longestPalindrome(String s) {
            int maxLen = 1;
            int n = s.length();
            
            for(int i = 0; i < n; i++) {
                // 奇数长度
                int l = i, r = i;
                while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    maxLen = Math.max(maxLen, r - l + 1);
                    l--; r++;
                }
                
                // 偶数长度
                l = i; r = i + 1;
                while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    maxLen = Math.max(maxLen, r - l + 1);
                    l--; r++;
                }
            }
            return maxLen;
        }
    }
    
    // Manacher算法
    static class Solution2 {
        public int longestPalindrome(String s) {
            StringBuilder t = new StringBuilder("$#");
            for(char c : s.toCharArray()) {
                t.append(c).append("#");
            }
            t.append("@");
            
            String str = t.toString();
            int n = str.length();
            int[] p = new int[n];
            int maxLen = 0;
            int center = 0, right = 0;
            
            for(int i = 1; i < n-1; i++) {
                if(i < right) p[i] = Math.min(right - i, p[2 * center - i]);
                
                while(str.charAt(i + p[i] + 1) == str.charAt(i - p[i] - 1)) p[i]++;
                
                if(i + p[i] > right) {
                    center = i;
                    right = i + p[i];
                }
                maxLen = Math.max(maxLen, p[i]);
            }
            return maxLen;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        Solution1 sol1 = new Solution1();
        // Solution2 sol2 = new Solution2();
        System.out.println(sol1.longestPalindrome(s));
    }
}

Python实现

# 朴素解法
def longest_palindrome1(s: str) -> int:
    max_len = 1
    n = len(s)
    
    for i in range(n):
        # 奇数长度
        l, r = i, i
        while l >= 0 and r < n and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
        
        # 偶数长度
        l, r = i, i + 1
        while l >= 0 and r < n and s[l] == s[r]:
            max_len = max(max_len, r - l + 1)
            l -= 1
            r += 1
    
    return max_len

# Manacher算法
def longest_palindrome2(s: str) -> int:
    t = '$#' + '#'.join(s) + '#@'
    n = len(t)
    p = [0] * n
    max_len = 0
    center = right = 0
    
    for i in range(1, n-1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        
        if i + p[i] > right:
            center = i
            right = i + p[i]
        max_len = max(max_len, p[i])
    
    return max_len

# 主程序
s = input().strip()
print(longest_palindrome1(s))  # 使用朴素解法
# print(longest_palindrome2(s))  # 使用Manacher算法

算法及复杂度

朴素解法

  • 时间复杂度： - 每个中心点向两边扩展
  • 空间复杂度： - 只需要常量额外空间

Manacher算法

  • 时间复杂度： - 线性时间复杂度
  • 空间复杂度： - 需要额外数组存储回文半径