5.Longest Palindromic Substring (String; DP, KMP)

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.

思路：动态规划，遍历到i的时候要保证之前的元素都已经计算过状态，所以遍历顺序同插入排序，时间复杂度O(n2)

class Solution {
public:
    string longestPalindrome(string s) {
      int len = s.length();
      if(len==0) return s;
      
      bool dp[len][len]={false};
      int maxLen=1;
      int start=0;
      
      //initialize
      for(int i = 0; i < len; i++){
          dp[i][i]=true;
      }
      
      for(int i=1; i<len; i++){
          for(int j = 0; j<i; j++){
              if(s[i]==s[j] && (j==i-1 || dp[j+1][i-1])){
                  dp[j][i]=true;
                  if(i-j+1 > maxLen){
                      maxLen=i-j+1;
                      start=j;
                  }
              }
          }
      }
      
      return s.substr(start, maxLen);
    }
};