寫在前面
這個題目之前在高中的時候就曾經寫過，現在到了研究所學生很多東西需要再重新撿起來的呢，在面試中也曾經兩次遇到這樣的題目，現在在今天2020年3月12日10:14:49統一整理一下，預計花費2個小時的時間。
題目描述
給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: “babad” 輸出: “bab” 注意: “aba” 也是一個有效答案。 示例 2：
輸入: “cbbd” 輸出: “bb”
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
方法一：最長公共子串
最大的回文子串，可以替換成最長公共子串，兩個字元串最長的公共的部分的，但是存在反向副本時，政策失效，需要補充條件進行判定，如果反向子串索引和原始索引相同則更新。
花了一個小時學習最長公共子串的算法，花了半個小時想出了序号的判别方法。時間複雜度O(n2) leetcode
不能AC最後一個樣例逾時。吃個飯繼續搞~
def longestPalindrome( s):
string1=s
string2=s[::-1]
len1 = len(string1)
len2 = len(string2)
res = [[0 for i in range(len1+1)] for j in range(len2+1)]
#python 初始化二維數組 [len1+1],[len2+1]
result =0
index=0
for i in range(1,len2+1): #開始從1開始，到len2+1結束
for j in range(1,len1+1): #開始從1開始，到len2+1結束
if string2[i-1] == string1[j-1]:
res[i][j] = res[i-1][j-1]+1
if (result<=res[i][j])& (len(string1)-i==j-res[i][j]):
index=j
result = res[i][j]
string=string1[index-result:index]
return string # 輸出
print(longestPalindrome("adabxxcbada"))
方法二：暴力法
方法三：動态規劃方法
動态規劃的方法，關鍵在于尋找邊界狀态。這個也不能AC，會逾時，關于數組邊界的問題，讓我體會了一把python的金穗。
def longestPalindrome(s):
if(s == ""): return s
strlen = len(s)
dp=[[False for i in range(len(s))] for j in range(len(s))]
for i in range(len(s)): dp[i][i] = True
for i in range(len(s)-1): dp[i][i+1] = (s[i] == s[i+1])
left = 0
right = 0
maxnum = 1;
for i in range(len(s)-2,-1,-1): #下左标 ，從0 開始 一定要倒置，否則計算出來的有問題，從小到大推過來的。
for j in range(1,len(s)): #下右标
# P(i,j)=(P(i+1,j−1) and Si==Sj)
if(i != j ) & (j != i+ 1):
dp[i][j] = dp[i+1][j-1] & (s[i] == s[j]);
if(dp[i][j]) & (maxnum < j - i + 1):
maxnum = j - i + 1;
left = i;
right = j;
print(i,j,dp[i][j])
return s[left:right+1];
print( longestPalindrome("ab"))
方法四：中心擴充法
解法五: Manacher’s Algorithm 馬拉車算法
馬拉車算法 Manacher‘s Algorithm 是用來查找一個字元串的最長回文子串的線性方法，由一個叫 Manacher 的人在 1975 年發明的，這個方法的最大貢獻是在于将時間複雜度提升到了線性。
首先我們解決下奇數和偶數的問題，在每個字元間插入 “#”，并且為了使得擴充的過程中，到邊界後自動結束，在兩端分别插入 “^” 和 “$”，兩個不可能在字元串中出現的字元，這樣中心擴充的時候，判斷兩端字元是否相等的時候，如果到了邊界就一定會不相等，進而出了循環。經過處理，字元串的長度永遠都是奇數了。
首先我們用一個數組 P 儲存從中心擴充的最大個數，而它剛好也是去掉 “#” 的原字元串的總長度。例如下圖中下标是 6 的地方，可以看到 P[ 6 ] 等于 5，是以它是從左邊擴充 5 個字元，相應的右邊也是擴充 5 個字元，也就是 “#c#b#c#b#c#”。而去掉 # 恢複到原來的字元串，變成 “cbcbc”，它的長度剛好也就是 5。
求原字元串下标
用 P 的下标 i 減去 P [ i ]，再除以 2，就是原字元串的開頭下标了。
例如我們找到 P[ i ] 的最大值為 5，也就是回文串的最大長度是 5，對應的下标是 6，是以原字元串的開頭下标是（6 - 5 ）/ 2 = 0。是以我們隻需要傳回原字元串的第 0 到 第（5 - 1）位就可以了。
求每個 P [ i ]
接下來是算法的關鍵了，它充分利用了回文串的對稱性。
我們用 C 表示回文串的中心，用 R 表示回文串的右邊半徑。是以 R = C + P[ i ]。C 和 R 所對應的回文串是目前循環中 R 最靠右的回文串。
讓我們考慮求 P [ i ] 的時候，如下圖。
用 i_mirror 表示目前需要求的第 i 個字元關于 C 對應的下标。
class Solution:
def center_spread(self, s,center):
size = len(s)
i = center - 1
j = center + 1
step = 0
while i >= 0 and j < size and s[i] == s[j]:
i -= 1
j += 1
step += 1
return step
def longestPalindrome(self,s):
# 特判 差一個空格，5個縮進的樣子
size = len(s)
if size < 2:
return s
# 得到預處理字元串
t = "#"
for i in range(size):
t += s[i]
t += "#"
# 新字元串的長度
t_len = 2 * size + 1
# 目前周遊的中心最大擴散步數，其值等于原始字元串的最長回文子串的長度
max_len = 1
# 原始字元串的最長回文子串的起始位置，與 max_len 必須同時更新
start = 0
for i in range(t_len):
cur_len = self.center_spread(t, i)
if cur_len > max_len:
max_len = cur_len
start = (i - max_len) // 2
return s[start: start + max_len]
正常縮進是5個空格，定義類的時候self.就是方法的函數，定義的函數需要放置在使用的函數之前，這一點和matlab不一緻，和Pascal比較一緻。