longest.py

class Solution(object):
	

    def preProcess(self,s):
    	if not s:
        	return ['^', '$']
    	T = ['^']
        for c in s:
            T +=  ['#', c]
        T += ['#', '$']
        return T

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        T = self.preProcess(s)
        P = [0] * len(T) 
        center, right = 0, 0
        for i in xrange(1, len(T) - 1):
            i_mirror = 2 * center - i
            if right > i:
                P[i] = min(right - i, P[i_mirror])
            else:
                P[i] = 0

            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1

            if i + P[i] > right:
                center, right = i, i + P[i]       
        
        max_i = 0
        for i in xrange(1, len(T) - 1):
            if P[i] > P[max_i]:
                max_i = i
        start = (max_i - 1 - P[max_i]) / 2
        return s[start : start + P[max_i]]

    
if __name__ == "__main__":
    print Solution().longestPalindrome("ABBC")