Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路：如果不用动态规划，在两个for循环的情况下，还得依次比较i，j间的每个字符，O(n3)。使用动态规划，O(n2)

char* longestPalindrome(char* s) {    int n = strlen(s);    int max = 1;    int pStart = 0;    bool flag[n][n];    for(int i = 0; i < n; i++){        flag[i][i] = true;        for(int j = i+1; j < n; j++){            flag[i][j] = false;        }    }        for(int j = 1; j < n; j++){ //when iterate j, we should already iterated j-1, 可以理解成j之前已排序好=>用插入排序的顺序遍历        for(int i = 0; i < j; i++){             if(s[i]==s[j]){                flag[i][j] = (j==i+1)?true:flag[i+1][j-1];                              if(flag[i][j] && j-i+1 > max){                                        max = j-i+1;                    pStart = i;                }            }        }    }    s[pStart+max]='\0';    return &s[pStart];}

 

方法II：KMP+动态规划，时间复杂度在最好情况下达到O(n)

首先在字符串的每个字符间加上#号。For example: S = “abaaba”, T = “#a#b#a#a#b#a#”。这样所有的回文数都是奇数，以便通过i的对应位置i’获得p[i]

P[i]存储以i为中心的最长回文的长度。For example: 

T = # a # b # a # a # b # a #

P = 0 1 0 3 0 1 6 1 0 3 0 1 0

下面我们说明如何计算P[i]。

假设我们已经处理了C位置（中心位置），它的最长回文数是abcbabcba，L指向它左侧位置，R指向它右侧位置。

现在我们要处理i位置。

if P[ i' ] ≤ R – i,

then P[ i ] ← P[ i' ] 那是因为在L到R范围内，i'的左侧与i的右侧相同，i'的右侧与i的左侧相同，i'左侧与右侧相同 =>i左侧与右侧相同。

else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to find P[ i ].

If the palindrome centered at i does expand past R, we update C to i, (the center of this new palindrome), and extend R to the new palindrome’s right edge.

char* preProcess(char* s) {    int n = strlen(s);    if (n == 0) return "^$";    char* ret = malloc(sizeof(char)*(n*2+4));    char* pRet = ret;    *pRet++ = '^'; //开始符^    for (int i = 0; i < n; i++){      *pRet++ = '#';      *pRet++ = s[i];    }    *pRet++ = '#';    *pRet = '$';//结束符$    return ret;} char* longestPalindrome(char* s) {    char* T = preProcess(s);    int n = strlen(T);    int P[n];     int C = 0, R = 0;    char* ret;    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]      if(R>i){          if(P[i_mirror] <= R-i){              P[i] = P[i_mirror];          }          else P[i] = R-i;      }      else P[i] = 0;            //else: Attempt to expand palindrome centered at i      while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) //因为有哨兵^$所以不用担心越界; +1, -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;      }    }        ret = malloc(sizeof(char)*maxLen+1);    strncpy(ret, s+(centerIndex - 1 - maxLen)/2, maxLen);    ret[maxLen] = '\0';    return ret;  }