最長回文字符串
????????????給定一個字符串?s蜜暑，找到?s?中最長的回文子串铐姚。
示例 1：
? ??輸入:"babad"
? ??輸出:"bab"
? ??注意:"aba" 也是一個有效答案。
示例 2：
? ??輸入:"cbbd"
? ??輸出:"bb"
? ? ? 解法有很多肛捍，①暴力破解法：可以枚舉所有可能的字符串子串隐绵，然后判斷是否為回文字符串。但這種解法的時間復(fù)雜度很高拙毫，首先是枚舉所有可能的子串依许，時間復(fù)雜度O(n2)，再判斷是否為回文字符串缀蹄，時間復(fù)雜度為O(n2)峭跳，總體的時間復(fù)雜度為O(n3)。②反轉(zhuǎn)法：將字符串反轉(zhuǎn)缺前，找出最長公共子串蛀醉，注意這兩段最長公共子串的位置應(yīng)該是關(guān)于中心對稱的，時間復(fù)雜度為O(n2)衅码。③動態(tài)規(guī)劃：動態(tài)規(guī)劃最重要的就是要找到狀態(tài)轉(zhuǎn)移方程拯刁，而回文的最大特點就是如果一個子串是回文，它兩側(cè)的字符如果相同逝段，那么加上這兩個字符組成的新字符串同樣也是回文垛玻，這種方法的時間復(fù)雜度同樣也是O(n2)割捅。④中心擴散法：遍歷字符串中所有的字符，以這些字符為中心夭谤，用兩個指針向外擴散棺牧，用一個數(shù)組來記錄擴散的半徑；這種方法使用起來有一個小缺陷朗儒，比如aba颊乘，abba兩種回文，前者這種方法很好用醉锄，但是后者就需要特別去判斷乏悄。為了解決這個問題，我們可以向每個字符之間插入一個相同的符號恳不，比如#a#b#b#a#檩小，這樣就很好解決了上述問題，這種方法的時間復(fù)雜度也為O(n2)烟勋。這些方法的時間復(fù)雜度都在O(n2)以上规求，但有一種算法它的時間復(fù)雜度為O(n)，就是馬拉車算法卵惦。
馬拉車算法：
維基百科中對于 Manacher 算法是這樣描述的：
[Manacher(1975)] 發(fā)現(xiàn)了一種線性時間算法阻肿，可以在列出給定字符串中從字符串頭部開始的所有回文。并且沮尿，Apostolico, Breslauer & Galil (1995) 發(fā)現(xiàn)丛塌，同樣的算法也可以在任意位置查找全部最大回文子串，并且時間復(fù)雜度是線性的畜疾。因此赴邻，他們提供了一種時間復(fù)雜度為線性的最長回文子串解法。替代性的線性時間解決 Jeuring (1994), Gusfield (1997)提供的啡捶，基于后綴樹(suffix trees)姥敛。也存在已知的高效并行算法。
Manacher 算法本質(zhì)上還是中心擴散法届慈，只不過它使用了類似 KMP 算法的技巧徒溪，充分挖掘了已經(jīng)進行回文判定的子串的特點，在遍歷的過程中金顿，記錄了已經(jīng)遍歷過的子串的信息，也是典型的以空間換時間思想的體現(xiàn)鲤桥。算法技巧：
①定義max_right來記錄當(dāng)前遍歷字符串中能到達最右邊的邊界為多少揍拆，定義id記錄達到最右邊界的字符串中心
②算法步驟和中心擴散法一致，但是在計算類似#a#b#c#d#e#d#c#b#a#時茶凳，因為回文字符串左右對稱嫂拴，所以當(dāng)你計算了左邊的P數(shù)組的值時播揪，右邊的計算是可以借鑒左邊的值，如下
通過增加參數(shù)筒狠，降低尋找次數(shù)猪狈，是典型的以空間換取時間的做法。
def Manacher(s):#回文字符串線性時間復(fù)雜度
? ? lenth =len(s)
????if lenth <2:#特判
? ? ? ? return s
????t ="#"
? ? for iin range(lenth):#初始化
? ? ? ? t = t + s[i]
????????t = t +"#"
????t_lenth =2 * lenth +1
? ? p = [0 for i in range(t_lenth)]#記錄擴散半徑
? ? max_right =0
? ? id =0
? ? max_lenth =0
? ? start =1
? ? for iin range(t_lenth):
????????if i < max_right:
????????????mirror =2 * id - i
????????????p[i] =min(p[mirror],max_right-i)
????????left = i - (1 + p[i])
????????right = i + (1 + p[i])
????????while left >=0 and right < t_lenthand t[left] == t[right]:
????????????p[i] = p[i] +1
? ? ? ? ? ? left = left -1
? ? ? ? ? ? right = right +1
? ? ? ? if i + p[i] > max_right:
????????????max_right = i + p[i]
????????????id = i
? ? ? ? if p[i] > max_lenth:
????????????max_lenth = p[i]
????????????start = (i - max_lenth) //2
? ? return s[start:start+max_lenth]
