5. 最长回文子串

描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例

示例 1：
  输入: "babad"
  输出: "bab"
  注意: "aba"也是一个有效答案。

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

思路

1. 回文串有两种形式，奇数和偶数形式的，可以依次遍历以每个字符为中心的两种形式的回文串，求出最长的一个即可。时间复杂度为O(n^2)
2. Manacher算法，时间复杂度为O(n)，能够理解其核心思维，但编程代码还需进一步深入了解。附上两个参考地址(参考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);
  }
};