#思路：动态规划 #   1、dp[i][j] = 1表示字符串s从i到j是回文串  dp[i][j] = 0表示字符串s从i到j不是回文串 #   2、如果dp[i][j] = 1， 那么dp[i+1][j-1] = 1


import sys

def manacher(s):

    maxlen = 0

    start = 0

    dp = [[0 for i in range(len(s))] for i in range(len(s))]

    for i in range(len(s)):

        dp[i][i] = 1

        if i+1<len(s) and s[i] == s[i+1]:

            dp[i][i+1] = 1

            maxlen = 2

            start = i

    for i in range(3,len(s)+1):

        for j in range(len(s)-i+1):

            k = i+j-1 

            if dp[j+1][k-1]==1 and s[j]==s[k]:

                dp[j][k] = 1

                if i>maxlen:

                    start = j

                    maxlen = i

    if maxlen>=2:

        return s[start:start+maxlen]

    return 1

for i in sys.stdin.readlines():

    print (manacher(i.strip()))


	

python 解法 时间复杂度为O(n)

理论支持：从头到尾扫描字符串，每当增加一个新的字母，最大回文串的长度只能增加1或者2，不可能增加更多，并且，新的最大回文串必然要包含这个字母！

证明：如果新增了一个字母，最大回文串的长度增加了3，这是不可能的，例如：abcdefgfedcba，当增加到最后的b或者a时，是不可能增加3个长度的，因为每增加一个字母，前面必然已经存在一个回文子串，且长度比新串小1或者小2.

所以，从头到尾扫描字符串，每增加一个新的字符，判断以这个字符结尾，且长度为maxLen+1或者maxLen+2的子串是否为回文，如果是，更新最大回文子串。

import sys


def longestPalindrome(s):
    if s == s[::-1]: return s
    start, maxLen = 0, 1
    for i in range(len(s)):
        if i - maxLen >= 1 and s[i - maxLen -1:i + 1] == s[i - maxLen - 1:i + 1][::-1]:
            start = i - maxLen - 1
            maxLen += 2
            continue
        if i - maxLen >= 0 and s[i - maxLen:i + 1] == s[i - maxLen:i + 1][::-1]:
            start = i - maxLen
            maxLen += 1
    return s[start:start + maxLen]


for i in sys.stdin.readlines():
    print (longestPalindrome(i.strip()))