5. Longest Palindromic Substring

5. Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Solution

马拉车算法,专门用于计算最大回文子字符串长度。

预处理

首先需要对字符串进行预处理,将每两个字符之间(包括两端)加上一个符号’#’。
然后在字符串的前后加入任意两个不同的符号。(防止中心扩展时继续搜索)

这个操作使得偶数项的回文字符串变为奇数项的回文字符串,便于接下来进行统一的中心扩展操作。

Manacher算法

参考资料:一文让你彻底明白马拉车算法

用一个数组p[]记录处理后字符串位置的中心展开长度。

初始化一个回文中心的下标位置i,和当前回文中心的右侧范围r。
在进行算法时维护这两个参数。

遍历字符串中除了首尾两个字符以外的位置。

  • 初始化i位置关于c的镜像位置m为2*c-i。
    由于回文字符串的对称特性,此时p[i]的中心拓展长度应等于p[m]。
  • 有几种特例情况,p[i]不等于p[m]:
  1. 如果p[m] + m的和大于r,则以m为中心扩展的范围超过当前c的中心扩展范围的右界。
    此时p[i]无法保证等于p[m]。但是可以确保p[i]至少可以扩展到r,因此将p[i]更新为r-i。
  2. 如果i的位置等于r,则可扩展距离为0。
  3. 如果m的位置为原字符串的左边界,则此时将p[i]赋值为1是不正确的。
    因为p[m]的计算是遇到了边界停止的,而p[i]则没有遇到边界,接下来对i位置从i+p[i]与i-p[i]开始继续进行中心扩展即可。

中心扩展

奇数项的回文字符串由中心扩展,只需要保证i+p[i]+1与i-p[i]-1(两个位置分别表示当前中心扩展的边缘再前进1)的字符相同,则可以继续向下扩展,将p[i]++。

c与r的更新

由于要保证i在r的范围之内,当从i出发的中心扩展范围大于c的中心扩展范围r,需要更新c与r。

时间复杂度

在进行扩展时,每次访问过的位置不会进入中心扩展算法。(比较从中心扩展的边缘开始,即i+p[i]+1与i-p[i]-1)
因此总的时间复杂度为O(n)。

Code

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
class Solution {
int n;
int[] p;
String newString;
public String longestPalindrome(String s) {
n = s.length();
StringBuffer sb = new StringBuffer();
if(n == 0) { //对字符串进行处理
sb.append("^$");
}
else{
sb.append("^");
for(int i = 0; i < s.length(); i++){
sb.append('#');
sb.append(s.charAt(i));
}
sb.append("#$");
}
p = new int[sb.length()];
newString = sb.toString();
manacher();

int c = 0;
for(int i = 0; i < sb.length(); i++){
if(p[i] > p[c]) c = i;
}
return s.substring( (c-p[c])/2, (c-p[c])/2+p[c] );
}

private void manacher(){
int c = 0, r = 0;
for(int i = 1; i < p.length - 1; i++){
int m = 2 * c - i;
if(i < r){ //当i在r的范围内时,p[i]的值与p[m]相等。
p[i] = Math.min(r-i, p[m]); //当p[m] + i超过了r时(当前中心拓展边界),p[i]至少可以取值到r-i
}
else{
p[i] = 0; //当i等于r时,该位置拓展距离为0
}

while (newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)) { //中心拓展算法,当两个位置相等时则可拓展距离+1
p[i]++;
}

if(i + p[i] > r){ //当当前位置的右侧边界大于现有边界时,更新位置r
c = i;
r = i + p[i]; //新的右侧边界为新的中心+拓展长度p[i]
}
}
}
}

Solution 2

getLength方法,计算每一个字符位置的回文长度。(将left填成i+1,right填成i则可以搜索偶数回文的长度。)
如果出现更长的回文,则根据返回的长度,和当前的i计算出字符串的范围。

Code

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
class Solution {
public String longestPalindrome(String s) {
int best = 0;
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++){
int length = Math.max(getLength(s,i,i), getLength(s,i+1,i));
if(best < length){
left = i-((length-1)/2-1);
right = i+(length/2);
best = length;
}
}
return s.substring(left,right);
}

private int getLength(String s, int left, int right){
while(left >= 0 && right < s.length() && left < s.length()){
if(s.charAt(left) == s.charAt(right)){
left--;
right++;
}
else break;
}

return right - left + 1;
}
}
Author

Xander

Posted on

2022-04-24

Updated on

2022-06-08

Licensed under

Comments