题解 | #密码截取#扩展最短回文子字符串

思路1（易超时，不推荐）：从输入字符串中截取子字符串a，先设定子字符串a长度等于输入字符串A的长度L，判断a若对称，返回结果为L；若a不对称，截取所有长度为L-1的子字符串：a1、a2，若a1、a2有一个对称，返回结果为L-1；若a1、a2均不对称，截取所有长度为L-2的子字符串：a1、a2、a3，若a1、a2、a3种有一个对称，返回结果为L-2；以此类推，可以找出最长的对称子字符串。由于需要两层循环嵌套，时间复杂度为:(n^2)/2

str1 = input()
n = len(str1)
l = 0
for i in range(n, 2, -1):
    for j in range(n-i+1):
        temp = str1[j:j+i]
        if temp == temp[::-1]:
            l = i
            break
    if l > 0:
        print(l)
        break

思路2：遍历输入字符串A，找到所有的最短对称子字符串（形式如：'AA'、'A*A'）及其位置，对每一个子字符串 a，向两侧逐步扩展，直至不再对称，得到字符串 a' (a' 包含 a)，记录 a'  的长度。如此就能找到输入字符串A中所有的对称子字符串，返回其中长度最大的子字符串的长度即可。时间复杂度：n

# 从最短对称子字符串两侧扩展，计算最大长度
def get_max_length(i, j):
    l = j - i + 1
    m = min(i, n-j-1)
    for k in range(1, m+1):
        if str1[i-k] == str1[j+k]:
            l += 2
        else:
            break
    return l

str1 = input()
n = len(str1)
result = []

# 找到所有最短的对称子字符串
for i in range(n-1):
    if str1[i] == str1[i+1]:
        l = get_max_length(i, i+1)
        result.append(l)
    if i < (n-2) and str1[i] == str1[i+2]:
        l = get_max_length(i, i+2)
        result.append(l)

print(max(result))