Python培训之找回文子串的方法

　　Python找回文子串的方法

　　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找回文子串的方法，希望对大家有所帮助。更多Python学习指路：请关注多测师。https://www.e70w.com/xwzx/