Java编程实战：深入解析“最长回文子串”问题
一、问题背景
回文子串，顾名思义，就是从字符串中任意位置截取的一段子串，该子串的左右对称字符相同，也就是正着读和倒着读都一样。例如，“abba”和“abcba”都是回文子串。在编程中，求解一个字符串的最长回文子串是一个常见的算法问题。
二、解决方案
解决“最长回文子串”问题，可以采用以下几种方法：
1. 动态规划法
2. 中心扩展法
3. Manacher算法
本文将重点介绍动态规划法和中心扩展法，并对Manacher算法进行简要说明。
三、动态规划法
动态规划法是一种常见的算法设计思想，它将一个复杂的问题分解成若干个互相重叠的子问题，然后将子问题的解存储在一张表中，最终合并所有子问题的解得到原问题的解。
以下是动态规划法解决“最长回文子串”问题的具体步骤：
（1）定义二维数组dp[i][j]，其中dp[i][j]表示从字符串的索引i到索引j的子串是否为回文。
（2）初始化：对于字符串中的每个字符，将其视为一个回文子串，即dp[i][i] = true。
（3）状态转移：对于长度大于等于2的子串，如果s[i] == s[j]，则dp[i][j] = dp[i + 1][j - 1]。否则，dp[i][j] = false。
（4）遍历dp数组，找出最大的i和j，使得dp[i][j] = true。此时，从i到j的子串就是最长回文子串。
以下是Java代码实现：
```java
public class LongestPalindromicSubstring {
public static String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (len > maxLength) {
start = i;
maxLength = len;
}
}
}
}
return s.substring(start, start + maxLength);
}
public static void main(String[] args) {
String input = "babad";
System.out.println("最长回文子串为：" + longestPalindrome(input));
}
}
```
四、中心扩展法
中心扩展法是一种基于回文对称性质的方法。回文串具有左右对称的特性，因此可以假设最长的回文子串的对称轴为字符串中的一个字符（或字符之间），然后向两侧扩展，寻找最长的回文子串。
以下是中心扩展法解决“最长回文子串”问题的具体步骤：
（1）定义一个变量maxLength表示最长回文子串的长度，初始值为1。
（2）定义一个变量start表示最长回文子串的起始位置，初始值为0。
（3）遍历字符串中的每个字符，将其作为对称轴的中间位置，向两侧扩展，计算回文子串的长度。
（4）如果计算出的长度大于maxLength，则更新maxLength和start的值。
以下是Java代码实现：
```java
public class LongestPalindromicSubstring {
public static String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int maxLength = 1, start = 0;
for (int i = 0; i < n - 1; i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > maxLength) {
maxLength = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLength);
}
private static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static void main(String[] args) {
String input = "babad";
System.out.println("最长回文子串为：" + longestPalindrome(input));
}
}
```
五、Manacher算法
Manacher算法是一种线性时间内求解最长回文子串的算法。它通过预处理字符串，将所有的字符都转换为"^#$"的形式，从而消除边界的影响，并减少对单个字符的判断。
以下是Manacher算法解决“最长回文子串”问题的具体步骤：
（1）将原字符串s插入"^#"符号，并计算新的字符串t的长度。
（2）定义一个数组P，用于存储以t中每个字符为中心的最长回文子串的长度。
（3）定义一个变量center和right，分别表示当前已经扩展到的最长回文子串的中心和右边界。
（4）遍历t中的每个字符，根据其左右对称的性质，计算出以该字符为中心的最长回文子串的长度，并更新center和right。
（5）遍历P数组，找到最长回文子串的长度。
以下是Java代码实现：
```java
public class LongestPalindromicSubstring {
public static String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
String t = preprocess(s);
int n = t.length();
int[] P = new int[n];
int center = 0, right = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * center - i;
if (i < right) {
P[i] = Math.min(right - i, P[i_mirror]);
}
while (t.charAt(i + 1 + P[i]) == t.charAt(i - 1 - P[i])) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
int maxLength = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLength) {
maxLength = P[i];
centerIndex = i;
}
}
return s.substring((centerIndex - maxLength) / 2, (centerIndex + maxLength) / 2);
}
private static String preprocess(String s) {
int len = s.length();
StringBuilder ret = new StringBuilder("^#");
for (int i = 0; i < len; i++) {
ret.append(s.charAt(i)).append("#");
}
ret.append('$');
return ret.toString();
}
public static void main(String[] args) {
String input = "babad";
System.out.println("最长回文子串为：" + longestPalindrome(input));
}
}
```
总结：
在解决“最长回文子串”问题中，动态规划法、中心扩展法和Manacher算法都是可行的方法。动态规划法时间复杂度为O(n^2)，空间复杂度为O(n^2)；中心扩展法时间复杂度为O(n^2)，空间复杂度为O(1)；Manacher算法时间复杂度为O(n)，空间复杂度为O(n)。在实际应用中，可根据问题的规模和需求选择合适的算法。
