python找回文子串的方法

1、雙指針兩邊擴(kuò)展

遍歷指針為i，j=i+1，i左移，j右移。判斷是否相等將長(zhǎng)度，下標(biāo)賦給臨時(shí)變量，最后切片返回。唯一的大坑。回文字符串長(zhǎng)度可以是奇數(shù)也可以是偶數(shù)。奇數(shù)的時(shí)候，內(nèi)層循環(huán)從i-1開始。邊界條件也需要處理好。

classSolution(object):

deflongestPalindrome(self,s):

"""

:types:str

:rtype:str

"""

n=len(s)

maxL,maxR,max=0,0,0

foriinrange(n):

#長(zhǎng)度為偶數(shù)的回文字符串

start=i

end=i+1

whilestart>=0andend

ifs[start]==s[end]:

ifend-start+1>max:

max=end-start+1

maxL=start

maxR=end

start-=1

end+=1

else:

break

#長(zhǎng)度為奇數(shù)的回文子串

start=i-1

end=i+1

whilestart>=0andend

ifs[start]==s[end]:

ifend-start+1>max:

max=end-start+1

maxL=start

maxR=end

start-=1

end+=1

else:

break

returns[maxL:maxR+1]

2、Manacher算法

由于在輸入預(yù)處理的步驟中，將所有的回文子字符已經(jīng)轉(zhuǎn)為奇數(shù)長(zhǎng)度。所以在下面的操作中，只需要將輸入的每一個(gè)字符，都當(dāng)做一個(gè)回文子字符的中心位即可。不需要考慮偶數(shù)長(zhǎng)度的回文子字符。

'''

@author:YizhouZhao

'''

#設(shè)置radius[i]=1,因?yàn)樽址旧硪彩且粋€(gè)回文數(shù)

radius[i]=1

while(string[i-radius[i]]==string[i+radius[i]]):

radius[i]+=1

以上就是Python找回文子串的方法，希望對(duì)大家有所幫助。更多Python學(xué)習(xí)教程請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。