前言

題目來(lái)源：

            
              記得一副有趣的對(duì)聯(lián): "霧鎖山頭山鎖霧, 天連水尾水連天", 上聯(lián)和下聯(lián)都是回文的.
當(dāng)然類似的還有: "上海自來(lái)水水來(lái)自海上, 山西懸空寺寺空懸西山".
回文是什么意思? 就是把內(nèi)容反過(guò)來(lái)讀也是和原來(lái)一樣的, 譬如 abccba, xyzyx, 這些都是回文的.
然而我們更感興趣的是在一個(gè)英文字符串 L 中, 怎么找出最長(zhǎng)的回文子串.
例如 L = "caayyhheehhbbbhhjhhyyaac", 那么它最長(zhǎng)的回文子串是 "hhbbbhh".
這個(gè)任務(wù)看似簡(jiǎn)單, 但是如果我告訴你 L 的長(zhǎng)度可能會(huì)接近 10^4, 問(wèn)題似乎就變麻煩了.
不管怎么說(shuō), 加油吧騷年.

            
          

實(shí)戰(zhàn)分析

網(wǎng)上關(guān)于最長(zhǎng)回文子串的題型主要包括輸出最長(zhǎng)回文子串，又或者輸出最長(zhǎng)回文子串的長(zhǎng)度，相對(duì)而言，后者更為簡(jiǎn)單。關(guān)于求解方法主要有四種，其一為暴力求解，最為直觀，不過(guò)時(shí)間復(fù)雜度也是最大的；其二為動(dòng)態(tài)規(guī)劃求解，時(shí)耗稍微好一點(diǎn)，關(guān)于動(dòng)態(tài)規(guī)劃案例分析，有興趣的朋友可以去動(dòng)態(tài)規(guī)劃學(xué)習(xí)(Python)了解一下；其三是中心擴(kuò)展；其四是 Manacher 法。關(guān)于后兩種方法可前往最長(zhǎng)回文子串 Python 四種解法進(jìn)行學(xué)習(xí)。

本文主要是從另個(gè)角度來(lái)對(duì)題目進(jìn)行求解，和中心擴(kuò)展法很像，但是時(shí)間復(fù)雜度更小。

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

def longestPalindrome():
    '''
    中心擴(kuò)展
    :return:
    '''
    global L1

    L = L1 + '#'

    maxlen = 0
    start = 0
    start_index_list = []#考慮到最長(zhǎng)回文子串存在多個(gè)值，這里記錄多個(gè)起點(diǎn)的索引
    index_dict = {}#用于存放字符串中每個(gè)字符連續(xù)出現(xiàn)的次數(shù)以及起始索引
    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

            
          

輸出結(jié)果為：

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