Noob
0%

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, and there exists one unique longest palindromic substring.
https://leetcode.com/problems/longest-palindromic-substring/

中心点扩散法

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 String longestPalindrome(String s) {
    if(s == null || s.length() == 0) return "";
    int maxLen = 0;
    String result = null;
    for(int i = 0; i < s.length(); ++i) {
        String tmp = getPalindrome(s, i, i);
        if(maxLen < tmp.length()) {
            maxLen = tmp.length();
            result = tmp;
        }
        tmp = getPalindrome(s, i, i + 1);
        if(maxLen < tmp.length()) {
            maxLen = tmp.length();
            result = tmp;
        }
    }
    return result;
}

private String getPalindrome(String s, int beg, int end) {
    while(beg >= 0 && end < s.length() && s.charAt(beg) == s.charAt(end)) {
        --beg;
        ++end;
    }
    return s.substring(beg + 1, end);
}

Manacher算法

  1. 对原字符串进行填充，使得每个字符都被两个’#’包围，这样处理，假设原字符串长度为n，那么处理后字符串长度为n + (n + 1) = 2 * n + 1，无论原字符串长度为奇数还是偶数，处理后的字符串长度一定是奇数，可以进行统一的处理。为了便于处理边界情况，在处理字符串头部和尾部分别插入两个不同于’#’的字符。
  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
public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) return "";
    String ps = process(s);
    int mx = 0, id = 0;
    int[] p = new int[ps.length()];
    for(int i = 1; i < ps.length() - 1; ++i) {
        p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
        while(ps.charAt(i + p[i]) == ps.charAt(i - p[i]))
            ++p[i];
        if(mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
    }
    int maxLen = 0, index = 0;
    for(int i = 1; i < ps.length(); ++i) {
        if(maxLen < p[i]) {
            maxLen = p[i];
            index = i;
        }
    }
    int beg = index - (maxLen - 1);
    int end = index + (maxLen - 1);
    return s.substring((beg - 1) / 2, (end - 1) / 2);
}

private String process(String s) {
    StringBuilder sb = new StringBuilder();
    sb.append('$');
    for(int i = 0; i < s.length(); ++i) {
        sb.append('#');
        sb.append(s.charAt(i));
    }
    sb.append('#');
    sb.append('^');
    return sb.toString();
}

参考资料

Longest Palindromic Substring 最长回文子串