前言

題目來源：

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

            
          

實戰(zhàn)分析

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

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

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

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

    L = L1 + '#'

    maxlen = 0
    start = 0
    start_index_list = []#考慮到最長回文子串存在多個值，這里記錄多個起點的索引
    index_dict = {}#用于存放字符串中每個字符連續(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']