5. Longest Palindromic Substring

Problem from leetcode 5. Longest Palindromic Substring

---

这道题是poj 3974 Palindrome和timus 1297. Palindrome的原题。
请参考1337c0d3r的解释。worst case time complexity is O(n) | space complexity is O(n)
原理大概和kmp类似。

---

class Solution {
public:
    // Transform S into T.
    // For example, S = "abba", T = "^#a#b#b#a#$".
    // ^ and $ signs are sentinels appended to 
    // each end to avoid bounds checking
    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' = C - (i-C) 
            P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
            // Attempt to expand palindrome centered at i
            while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
                P[i]++;
 
            // If palindrome centered at i expand past R,
            // adjust center based on expanded palindrome.
            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);
    }
};

Java:

class Solution {
    private static String preProcess(String s){
        if(s.length() == 0)
            return new String("^$");
        StringBuilder a = new StringBuilder("^");
        for(int i = 0; i < s.length(); i++)
        {
            a.append("#");
            a.append(s.substring(i, i+1));
        }
        a.append("#$");
        return a.toString();
    }
    
    public static 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' = C - (i-C) 
            P[i] = (R > i) ? Math.min(R-i, P[i_mirror]) : 0;
    
            // Attempt to expand palindrome centered at i
            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i]))
                P[i]++;
 
            // If palindrome centered at i expand past R,
            // adjust center based on expanded palindrome.
            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;
            }
        }
  
        return s.substring((centerIndex - 1 - maxLen)/2, (centerIndex-1-maxLen)/2 + maxLen);
    }
}