算法练习3

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.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

解题思路

题目大意是求最长回文子串。对于每个回文字符串，都有它们各自的中心，奇数回文的中心是一个字符，偶数回文的中心是两个字符，从中心向两边数就可以得到回文的长度。那么以字符串的每个字符或者每两个字符作为中心向两边扩散，就可以得到每个回文子串的长度，取其中最大的作为解。

当然解决最长回文子串还有一个O(n)的算法：Manacher算法。这个算法首先用到了一个很巧妙的方式将可能是奇数或者是偶数的回文子串都转换成了奇数长度：在每个字符两边都插入一个特殊字符。如abba变成#a#b#b#a#，aba变成#a#b#a#。然后用一个数组元素P[i]来记录以字符s[i]为中心的最长回文子串向左/右扩张的长度。

S  #  a  #  b  #  b  #  a  #  b  #  c  #  b  #  a  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
可以看出，P[i]-1正好是原字符串中回文串的总长度, i是原字符在S中的下标

然后就是这个算法的关键点，利用回文的对称性即左边是右边的镜像来计算P[i]，设两个辅助变量id和mx，其中id为已知有边界最大回文子串的中心，mx为id+p[id]，也就是这个子串的右边界。如果mx > i，那么p[i] >= min(P[2 * id - i], mx - i)。2*id-i是i关于id的对称点，上面的意思就是如果i在最大子串里面，mx-i是i到右边界的距离，如果i对称点的回文长度小于mx-i，那P[i]==P[2 * id - i]; 如果mx-i更小，那么意味着i的右边界超出了mx，那么P[i]>mx - i,超出部分不一定和i的对称点的那部分相同。对于mx <= i的情况，设P[i]=1，然后再去匹配。

代码

//我的解法
public class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = center(s, i, i);//奇数回文
            int len2 = center(s, i, i + 1);//偶数回文
            int len = len1 > len2 ? len1 : len2;
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int center(String s, int left, int right) {
        int l = left, r = right;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

//Manacher算法，代码来自http://articles.leetcode.com/longest-palindromic-substring-part-ii
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#$";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  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-i; // equals to i' = C - (i-C)
    
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    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;
    }
  }
  delete[] P;
  
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}