Python 求解最长回文子串

前言

题目来源：

            
              记得一副有趣的对联: "雾锁山头山锁雾, 天连水尾水连天", 上联和下联都是回文的.
当然类似的还有: "上海自来水水来自海上, 山西悬空寺寺空悬西山".
回文是什么意思? 就是把内容反过来读也是和原来一样的, 譬如 abccba, xyzyx, 这些都是回文的.
然而我们更感兴趣的是在一个英文字符串 L 中, 怎么找出最长的回文子串.
例如 L = "caayyhheehhbbbhhjhhyyaac", 那么它最长的回文子串是 "hhbbbhh".
这个任务看似简单, 但是如果我告诉你 L 的长度可能会接近 10^4, 问题似乎就变麻烦了.
不管怎么说, 加油吧骚年.

            
          

实战分析

网上关于最长回文子串的题型主要包括输出最长回文子串，又或者输出最长回文子串的长度，相对而言，后者更为简单。关于求解方法主要有四种，其一为暴力求解，最为直观，不过时间复杂度也是最大的；其二为动态规划求解，时耗稍微好一点，关于动态规划案例分析，有兴趣的朋友可以去动态规划学习(Python)了解一下；其三是中心扩展；其四是 Manacher 法。关于后两种方法可前往最长回文子串 Python 四种解法进行学习。

本文主要是从另个角度来对题目进行求解，和中心扩展法很像，但是时间复杂度更小。

            
              # L1 = 'caayyhheehhbbbhhjhhyyaac'
# L = 'aabbbaa'
L1 = 'babadcac'

def longestPalindrome():
    '''
    中心扩展
    :return:
    '''
    global L1

    L = L1 + '#'

    maxlen = 0
    start = 0
    start_index_list = []#考虑到最长回文子串存在多个值，这里记录多个起点的索引
    index_dict = {}#用于存放字符串中每个字符连续出现的次数以及起始索引
    for i in range(len(L)):
        if i >= sum(index_dict.values()):
            for j in range(i+1,len(L)+1):
                if len(set(L[i:j])) != 1:
                    index_dict[i] = len(L[i:j-1])
                    break

    for k,v in index_dict.items():
        i = k - 1
        j = k + v
        while i >= 0 and j < len(L):
            if L[i] == L[j]:
                if maxlen < j - i + 1:
                    maxlen = j - i + 1
                    start = i
                elif maxlen == j - i + 1:
                    start_index_list.append(i)
                i -= 1
                j += 1
            else:
                break

    start_index_list.insert(0,start)
    if maxlen >= 2:
        return [L[index:index+maxlen] for index in start_index_list]
    return None

            
          

输出结果为：

            
              ['hhbbbhh']
['bab', 'aba', 'cac']