Manacher算法 ,用于處理最長回文字符串的問題，可以在O（n）的情況下，求出一個字符串的最長回文字符串
回文串的基礎解法：
以每個點為中心對稱點，看左右兩邊的點是否相同。這種算法的時間復雜度為O（n^2），并且奇偶字符串的中心點是不同的。因此在處理時，可以在字符串的中間加上特殊字符，以使其都變成奇字符串，列如字符串：abba可以變成：#a#b#b#a#,字符串aba可以變成：#a#b#a#這樣無論對于奇字符串還是偶字符串都變成同樣的處理邏輯了。具體實現代碼如下所示：
data = "#"+"#".join(data)+"#"
n = len(data)
res = 0
for i in range(1,n-1):temp = 0l = i-1r = i+1while l>0 and r<n:if data[l] == data[r]:temp += 1l-=1r+=1else:res = max(res,temp)breakres = max(res,temp)
print(res)
馬拉車算法
馬拉車算法同樣使用特殊字符做預處理。首先先講解一下馬拉車算法的原理。對于字符串bcbabcc來說，通過處理可以將其變成 ^#b#c#b#a#b#c#c#$
我們使用一個數組p來記錄每個字符的可以擴展長度。比如第一個字符c來說，以c為中心點，分別判斷其左邊的字符和右邊的字符是否相等，看以c為中心點的最長回文字符串是3。即p[4]=3。
接下來，我們用c,r 兩個字符來分別表示中心點和可擴展到最右邊的長度。當我們以c為中心點時，其c為4，r為7。
根據回文字符串的特性來說，回文字符串的左邊必定是等于右邊的。因此以c為中心左邊的三個字符的p值一定是等于以c為中心右邊三個字符的p值的。
從1開始遍歷字符串，初始化c=0，r=0，p=[0]*字符串長度,
有三種情況：
1、遍歷的下標大于r：此時前面回文字符串的特性不能用，因此需要找到以該下標為中心點，向左向右判定p[i]的值
2、遍歷的下標小于r：根據回文字符串的特性，可以直接填充，比如·當我們遍歷到底一個字符c時，前面p的值為0,0,1,0,3.此時中心值為4，r為7，則由回文字符串的特性可以直接將后面的三個進行對稱填充為010。另一點需要注意的是，不能單純的進行對稱填充還要考慮范圍。如果對稱的值大于可覆蓋的范圍是不可取的。
具體的python實現代碼為：
def manacher(li):n = '^#' + '#'.join(li) + '#$'c = 0r = 0p = [0] * len(n)for i in range(1, len(n) - 1):##在邊界內if i <= r:p[i] = min(p[2 * c - i], r - i)##判斷左右是否相等while n[i - (1 + p[i])] == n[i + (1 + p[i])]:p[i] += 1##超出邊界，重新定義邊界和中心點if p[i] + i > r:r = p[i] + ic = ireturn max(p)
li = input()
print(manacher(li))
參考文章：
徹底搞懂馬拉車（Manacher）
參考視頻：
b站馬拉車算法
