5.Longest Palindromic Substring (String; DP)

class Solution {
public:
  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_mirror = C - (i-C)
    
      //if p[i_mirror] < R-i: set p[i] to p[i_mirror]
      P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
      //else: Attempt to expand palindrome centered at i
      while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) //因为有哨兵^$所以不用担心越界
        P[i]++;
      
      //if the palindrome centered at i does expand past R
      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);
  }
};