怎么在Python中找回文子串

怎么在Python中找回文子串？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

Python主要用來做什么

Python主要應用于：1、Web開發；2、數據科學研究；3、網絡爬蟲；4、嵌入式應用開發；5、游戲開發；6、桌面應用開發。

1、雙指針兩邊擴展

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

class Solution(object):
        
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        maxL, maxR, max = 0, 0, 0
        for i in range(n):
            # 長度為偶數的回文字符串
            start = i
            end = i + 1
            while start >= 0 and end < n:
                if s[start] == s[end]:
                    if end - start + 1 > max:
                        max = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
    
            # 長度為奇數的回文子串
            start = i - 1
            end = i + 1
            while start >= 0 and end < n:
                if s[start] == s[end]:
                    if end - start + 1 > max:
                        max = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
        return s[maxL:maxR+1]

2、Manacher算法

由于在輸入預處理的步驟中，將所有的回文子字符已經轉為奇數長度。所以在下面的操作中，只需要將輸入的每一個字符，都當做一個回文子字符的中心位即可。不需要考慮偶數長度的回文子字符。

'''
@author: Yizhou Zhao
'''
# 設置 radius[i] = 1, 因為字符本身也是一個回文數
radius[i] = 1
while(string[i-radius[i]] == string[i+radius[i]]):
    radius[i] += 1

看完上述內容，你們掌握怎么在Python中找回文子串的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！