【題解】LeetCode 5. Longest Palindromic Substring

class Solution {
public:
    string longestPalindrome(string s) {
        int l = s.length(), dp[l*2+5], mxr, mxp, idx = 0;
        string ans = "";
        memset(dp, 0, sizeof(dp));
        char ss[l*2+5];
        ss[0] = '#';
        ss[1] = '#';
        for (int i = 0; i < l; i++){
            ss[i*2+2] = s[i];
            ss[i*2+3] = '#';
        }
        l *= 2;
        mxr = 0;
        mxp = 0;
        for (int i = 1; i <= l; i++){
            if (i <= mxr){
                dp[i] = min(dp[mxp*2-i], mxr-i);
            }
            if (i + dp[i] >= mxr){
                while (ss[i+dp[i]+1] == ss[i-dp[i]-1]) dp[i]++;
            }
            if (i+dp[i] > mxr){
                mxr = i+dp[i];
                mxp = i;
            }
            if (dp[i] > dp[idx]) idx = i;
        }
        for (int i = idx-dp[idx]; i <= idx+dp[idx]; i++){
            if (ss[i] != '#'){
                ans += ss[i];
            }
        }
        return ans;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int ansi = 0, ansj = 0;
        int l = s.length();
        if (l == 0) return "";
        int a[l][l];
        memset(a, 0, sizeof(a));
        for (int i = 0; i < l; i++){
            a[i][i] = 1;
        }
        for (int i = 0; i < l-1; i++){
            if (s[i] == s[i+1]){
                a[i][i+1] = 1;
                ansi = i;
                ansj = i+1;
            }
        }
        for (int j = 2; j < l; j++){
            for (int i = 0; i < l-j; i++){
                if (a[i+1][i+j-1] == 1 && s[i] == s[i+j]){
                    a[i][i+j] = 1;
                    ansi = i;
                    ansj = i+j;
                }
            }
        }
        return s.substr(ansi, ansj-ansi+1);
    }
};