题解 | #最长回文子串#

这道题我不理解，也不了解manacher算法。先这样吧，回头再看不浪费时间了。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
      int length = A.size();
      //  源字符串全部变为偶数个字符，加上头两位。最后有指向回文串最右一位的下一位，故组合出来的字符串实际个数为偶数个
      std::vector<int> mp(2 * length + 2);
      int max_len = 0;
      
      manacher(A, length, mp);
      
      for (int i = 0; i < 2 * length + 2; ++i) {
        //  为什么减一
        //  减一是否由于是最右的下一位
        //  减一是因为中间一位算多一位？
        max_len = std::max(max_len, mp[i] - 1);
      }
      
      return max_len;
    }
  private:
  void manacher(std::string &str, int length, std::vector<int> &mp) {
    std::string s = "";
    s += "$#";
    
    //  变成偶数？
    for (int i = 0; i < length; ++i) {
      s += str[i];
      s += '#';
    }
    
    //  最长回文子串最右一位的后一位
    int max_pos = 0;
    //  当前最长回文子串的中心点
    int idx = 0;
    
    for (int i = 0; i < s.size(); ++i) {
      //  max_pos - i 不用加一，因为max_pos指向最右的下一位
      //  max_pos <= i 则是刚开始的情况
      //  mp[i] 计算的是最长回文子串的一半长度，因为原字符串被扩大了一倍
      mp[i] = max_pos > i ? std::min(mp[2 * idx - i], max_pos - i) : 1;
      //  两边扫描
      while (s[i + mp[i]] == s[i - mp[i]]) {
        ++mp[i];
      }
      //  更新位置
      //  mp[i] 表示的长度包含i本身，所以max_pos指向最右字符的下一位
      if (i + mp[i] > max_pos) {
        max_pos = i + mp[i];
        idx = i;
      }
    }
  }
};