Longest Palindromic Substring

• Time : $O(|A|)$
• Space : $O(|A|)$

string Solution::longestPalindrome(string A) {
    string s = "#";
    for(auto a : A) {
        s.push_back(a);
        s.push_back('#');
    }
    int n = s.length(), l = 0, r = -1;
    vector<int> dp(n);
    int p = -1, len = -1;
    for(int i = 0; i < n; i++) {
        dp[i] = max(0, min(r - i, r + l - i >= 0 ? dp[r + l - i] : -1));
        while(i + dp[i] < n and i - dp[i] >= 0 and s[i + dp[i]] == s[i - dp[i]]) dp[i]++;
        if(r < i + dp[i]) {
            r = i + dp[i];
            l = i - dp[i];
        }
        if(dp[i] * 2 - 1 > len) {
            len = dp[i] * 2 - 1;
            p = i;
        }
    }
    string res = "";
    for(int i = p - dp[p] + 1; i < p + dp[p]; i++) {
        if(s[i] != '#') res.push_back(s[i]);
    }
    return res;
}