```
def suffix_array(s):
return [s[i:] for i in xrange(len(s)-1)]
def count_prefix(a, b):
if a[1] == b[1]:
return 0
cnt = 0
for i in range(min(len(a[0]), len(b[0]))):
if a[0][i] == b[0][i]:
cnt += 1
return cnt
class Solution:
# @return a string
def longestPalindrome(self, s):
n = len(s)
S = s
R = s[::-1]
s_sfx = zip(suffix_array(S), [0] * n)
r_sfx = zip(suffix_array(R), [1] * n)
lst = sorted(s_sfx + r_sfx, key=lambda t: t[0])
m_len = 0
m_str = ''
for i in range(len(lst)-1):
l = count_prefix(lst[i], lst[i+1])
if l > m_len:
m_len = l
m_str = lst[i][0][:m_len]
return m_str
if __name__ == '__main__':
print Solution().longestPalindrome(raw_input().strip())
```

if n^2 solution can pass the test in C+/Java, I suggest to loose the time limit when code written in Python :-)