ARTS 第 5 周

每周一道算法、点评一篇英文技术文章、学习一个技术技巧、分享一个技术观点和思路

Algorithm

Problem: Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路 1

枚举中心位置,然后再在该位置上用扩展法

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
class Solution {
public static String longestPalindrome(String s) {
char[] chars = s.toCharArray();
int start = 0, end = 0;
int length = chars.length;
for (int i = 0; i < length; i++) {
// odd
for (int j = 0; (i - j >= 0) && (i + j < length); j++) {
if (chars[i - j] != chars[i + j]) {
break;
}
if (2 * j > end - start) {
start = i - j;
end = i + j;
}
}
// even
for (int j = 0; (i - j >= 0) && (i + j + 1 < length); j++) {
if (chars[i - j] != chars[i + j + 1]) {
break;
}
if (2 * j + 1 > end - start) {
start = i - j;
end = i + j + 1;
}
}
}
return s.substring(start, end + 1);
}
}

看到一个很简单的思路

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
public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;

for (int i = 0; i < len - 1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i + 1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
}

Review & Tip

最长回文子串的另外一种算法:Manacher’s Algorithm

算法第一个优点,用“#“分割字符串,将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#aba 变成 #a#b#a#

现有

1
S = "abaaba"

1
T = "#a#b#a#a#b#a#"

然后用一个数据 P,用 P[i] 来记录以 T[i] 中心最长的回文子串左边或右边的长度。

1
2
T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

可以看出 P[i] 正好是原字符串中最长回文串的总长度,所以 abaaba 的最长回文子串是 P[6] = 6

这就是算法的第二个优点,用已知的回文子串长度计算后面回文子串的长度。

那是怎么计算的呢?

现有 S = "babcbabcbaccba"

数组 P 已经完成了一部分,已知垂直实线表示回文 abcbabcba 的中心 C,两条垂直虚线分别表示其左 LR 边缘。

假设现在 i = 13,我们需要计算 P[13] 的值。

因为,从 LR 是以 C 为轴对称,所以 P[13] 也应该与 P[9] 是对称点,所以 P[13] = P[9] = 1

我们看 i=15 时,P[15] 的值

安装上面的对称原理,所有 P[15] = P[7] = 7?如果我们以 T[15] 为中心,发现回文是 #a#b#c#b#a#,比 7 小。

[0,14] 以 C 为对称轴的映射为 [8,22]。两条绿实线所表示的字符串必须完全匹配,绿虚线也是对称。而 P[i'] 它的回文一直延伸到 L 的左边(左红实线)。所以 P[i] 的值 ≥ 5 (因为 [2,7] 和 [15,20] 还是对称的)。至于 P[i] 的具体值,则需要继续往 R 延伸匹配。由于 P[21] != P[1],所以 P[i] = 5

所有这个算法的关键点是:

1
2
3
if P[i'] ≤ R - i
then P[i] = P[i']
else P[i] 大于等于 R - i

代码如下:

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
public static String longestPalindrome(String s) {
char[] T = preProcess(s).toCharArray();
int n = T.length;
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - 1;// i' = C - (i-C)
int p_mirror = 0;
if ((i_mirror >= 0 && i_mirror < n)) {
p_mirror = P[i_mirror];
}
P[i] = (R > i) ? Math.min(R - i, p_mirror) : 0;
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - 1 - maxLen) / 2;
return s.substring(start, start + maxLen);
}
public static String preProcess(String s) {
//^和$符号是附加到每一端的标记,以避免边界检查
int n = s.length();
if (n == 0) return "^$";
String ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substring(i, i + 1);
ret += "#$";
return ret;
}

Share

最近懒了,什么事都要拖到最后才去做,做事的时候容易被其他事情吸引,得改。

(完)