5. 最長(zhǎng)回文子串

描述

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為1000。

示例

示例 1：
  輸入: "babad"
  輸出: "bab"
  注意: "aba"也是一個(gè)有效答案。

示例 2：
  輸入: "cbbd"
  輸出: "bb"

思路

1. 回文串有兩種形式，奇數(shù)和偶數(shù)形式的，可以依次遍歷以每個(gè)字符為中心的兩種形式的回文串，求出最長(zhǎng)的一個(gè)即可。時(shí)間復(fù)雜度為O(n^2)
2. Manacher算法，時(shí)間復(fù)雜度為O(n)，能夠理解其核心思維，但編程代碼還需進(jìn)一步深入了解。附上兩個(gè)參考地址(參考1)(參考2)

class Solution_05_01 {
 public:
  string longestPalindrome(string s) {
    int cnt = 0;
    string ret;
    if (s.empty()) return ret;
    for (int i = 0; i < s.size(); ++i) {
      int start = i, end = i + 1;
      while (start >= 0 && end < s.size() && s[start] == s[end]) {
        --start;
        ++end;
      }
      int tmp = end - start - 1;
      if (tmp > cnt) {
        cnt = tmp;
        ret.clear();
        for (int j = start + 1; j <= end - 1; ++j) ret.push_back(s[j]);
      }
    }
    for (int i = 0; i < s.size(); ++i) {
      int start = i - 1, end = i + 1;
      while (start >= 0 && end < s.size() && s[start] == s[end]) {
        --start;
        ++end;
      }
      int tmp = end - start - 1;
      if (tmp > cnt) {
        cnt = tmp;
        ret.clear();
        for (int j = start + 1; j <= end - 1; ++j) ret.push_back(s[j]);
      }
    }
    return ret;
  }
};

class Solution_05_02 {
 public:
  string longestPalindrome(string s) {
    string manaStr = "$#";
    for (char ch : s) {
      manaStr += c;
      manaStr += '#';
    }
    vector<int> rd(manaStr.size(), 0);
    int pos = 0, mx = 0;
    int start = 0, maxLen = 0;
    for (int i = 1; i < manaStr.size(); i++) {
      rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1;
      while (manaStr[i + rd[i]] == manaStr[i - rd[i]]) rd[i]++;
      if (i + rd[i] > mx) {
        pos = i;
        mx = i + rd[i];
      }
      if (rd[i] - 1 > maxLen) {
        start = (i - rd[i]) / 2;
        maxLen = rd[i] - 1;
      }
    }
    return s.substr(start, maxLen);
  }
};