最长回文子串（英语：Longest palindromic substring）是计算机科学中的问题，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。
回文串的判断
1
2
3
4
5
6
7
8
9
10
11
12
13
|
boolean isPalindromicString(String s) {
int left = 0;
int right = s.length;
while(left < right) {
if (s[left] == s[right]) {
left++;
right++;
} else {
return false;
}
}
return true;
}
|
如果字符串 {s 的一个回文子串 s1 是 s 所有回文子串中长度最长的，那么则称 s1 为 s 的最长回文子串。
leetcode 最长回问子串
中心扩展法
遍历每一个字符，向两边扩展找到以其为中心的最长回文子串， 所有找到的回文子串的最大长度即所求 。
不过，以当前字符为中心的回文串的长度可能是奇数，也可能是偶数
两种情况的扩展起始点和回文串的计算方式是不同的。
显然，这种方法的时间复杂度是
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
public class LongestPalindromicSubsequence {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
|
一维动态规划
二维动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int longestPalindrome(String str) {
int n = str.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (str.charAt(i) == str.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
//
}
}
return dp[0][n - 1];
}
|
Manacher
要在线性时间内找出字符串的最长回文子串，这个算法必须利用回文字符串和子回文字符串中观察到的一些特点。
首先我们观察一下回文字符串可知，回文字符串都是对称的。而且如果一个长回文字符串的对称点左面包含一个小的回文字符串，那么对称过去到右面也必然会包含一个小的回文字符串，比如“dacabacad”这个字符串中，对称点b左面有一个回文字符串“aca”，右面也会对称出一个回文字符串“aca”。
时间复杂度 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
// 生成新的辅助String, eg: abc123成为#a#b#c#1#2#3#2#1#
public static char[] manacherStringString(String str) {
char[] c = str.toCharArray();
char[] res = new char[c.length * 2 + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
// 两个一样效果, 填充符号"#"
res[i] = (i % 2) == 0 ? '#' : c[index++];
// res[i] = (i & 1) == 0 ? '#' : c[index++];
}
return res;
}
// 返回最长回文串长度
public static int maxLcpsLength(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] charArr = manacherStringString(str);
// 辅助回文长度数组, 表示最多能扩充多少
int[] pArr = new int[charArr.length];
// 中心点
int C = -1;
// 最右边界
int R = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i != charArr.length; i++) {
// i在右边界内, i`到C的长度和到i到R的距离, 哪个小, 哪个就是起码成为回文的区域
// 否则为1, 自身
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
// 检查边界
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
// 左右字母相等, 扩1, 直到不能扩为止
pArr[i]++;
} else {
// 不能扩
break;
}
}
// 如果大于R, 那更新回文右边界和中心点
if ((i + pArr[i]) > R) {
R = i + pArr[i];
C = i;
}
// 如果需要, 则更新max
max = Math.max(max, pArr[i]);
}
// 返回最大回文长度
return max - 1;
}
```
## 总结
最容易理解的思路是中心扩展法。 时间表现最好的是 Manacher 方法。
中心扩展法和 Manacher算法 是针对回文串问题的具体算法，动态规划的思想则更具一般性。
|