題目：Longest Palindromic Substring
題目簡(jiǎn)述
找出最長(zhǎng)回文子串卿叽，如輸入"babad"，結(jié)果為"bab"或"aba"啤呼。
馬拉車算法
引入
可以觀察到回文串根據(jù)中心對(duì)稱吧兔，反之可以從中心向兩邊擴(kuò)張去尋找最大回文串。一共有2n+1個(gè)中心浊竟，每個(gè)都嘗試一下便可以得出答案。為了操作方便津畸，添加分隔符#振定。
如：babaabac——> #b#a#b#a#a#b#a#c
T為加分割符后的字符串，L[i]代表以T[i]為中心的最長(zhǎng)回文子串的長(zhǎng)度肉拓。最后找出最大的L為13后频，（13-1）/2后為原字符串的最長(zhǎng)回文子串的長(zhǎng)度。
上述算法時(shí)間復(fù)雜度為O(n2）,在具體求解每個(gè)L[i]時(shí)都需要O(n)的時(shí)間復(fù)雜度暖途，有沒有辦法可以提高效率呢卑惜？
若從左向右遍歷求解，回文串的特性可以發(fā)揮一定作用驻售。設(shè)L[0]-L[8]已求出露久，且已經(jīng)得知T[8]為中心,左邊界為T[2],右邊界為T[14]是回文串。那么接下來(lái)L[9]=L[7]=3,L[10]=L[6]=1,.....欺栗，但注意L[3]!=L[13]毫痕。具體分析看下文。
根據(jù)回文特性簡(jiǎn)化
若前面已經(jīng)求出了以C為中心迟几，R為右邊界的某個(gè)回文串消请，現(xiàn)在正要求的以i為中心的最大回文串長(zhǎng)度。若i<=R类腮，則可以根據(jù)對(duì)稱規(guī)則求解臊泰，若i>R則只能蠻力求解。
設(shè)P為回文半徑蚜枢，即表示以字符T[i]為中心的最長(zhǎng)回文字串的最端右字符到T[i]的長(zhǎng)度因宇。注：P[i]-1 即為原回文子串的長(zhǎng)度
四種情況
i>R
T[i-1]與T[i+1]匹配...T[i-2]與T[i+2]匹配...直至超出字符串邊界七婴，或T[i-k]!=T[i+k]i<=R且i+(P[i']-1)<R
P[i] = P[i']-
i<=R且i+(P[i']-1)>R
P[i] = R-i+1
例:如下圖，由于T[15]!=T[11]回文串被截?cái)?/p>
截?cái)?jpg
有沒有可能T[15]==T[11]呢察滑？
若T[15]=T[11]（已知T[11]=T[5]=T[1]），則T[1]=T[15]修肠，P[8]=7+1與P[8]=7矛盾贺辰，所以T[15]不可能等于T[11]。因此一定會(huì)被截?cái)唷?/p> i<=R且i+(P[i']-1)=R
P[i]>=R-i+1
首先嵌施，P[i]至少可以是R-i+1饲化，后面可能會(huì)有其他的字符使得回文子串繼續(xù)加長(zhǎng)，但也可能沒有吗伤。具體有沒有需要再一一匹配吃靠，但匹配的基礎(chǔ)是R-i+1。T[i-(R-i+1)]與T[(i+(R-i+1)]匹配..T[i-(R-i+2)]與T[(i+(R-i+2)]匹配...
Python代碼
class Solution:
def longestPalindrome(self, s: str) -> str:
c = 0
r = -1
T = '#' + '#'.join(s) + '#'
P = [1]*(len(T))
max_index = 0
for i in range(len(T)):
if i<= r:
P[i] = min(r-i+1,P[2*c-i])
# Try to extend
while i-P[i]>=0 and i+P[i]<len(T) and T[i+P[i]]==T[i-P[i]]:
P[i] += 1
# 循環(huán)中順便找出最長(zhǎng)回文子串的中心
if P[i]>P[max_index]:
max_index = i
if i+P[i]-1 >r:
c = i
r = i+P[i]-1
#根據(jù)映射關(guān)系返回原子串
return(s[(max_index-P[max_index]+2)//2:(max_index+P[max_index]-2)//2+1])
if __name__ == "__main__":
l = 'babad'
t = Solution()
r = t.longestPalindrome(l)
print(r)
總結(jié)
- 通過(guò)加分割符的方法足淆，使每個(gè)中心位置都可以取到巢块，也使字符串長(zhǎng)度統(tǒng)一為奇數(shù)
- 馬拉車算法主要運(yùn)用的是回文串的特性
