简单的中心扩散算法, 就不再赘述, 但是看了官方题解中的马拉车, 想到, 其实中心扩散是可以优化到 on 时间复杂度的, 尤其是在大数量级字符串时, 先上对比图, 字符串长度为 100w 和 1000w, 随机非回文长度和回文长度为 1k,1k 和 1w,1w, 上下分别为笔者算法和马拉车算法
思路就是, 如普通中心扩散算法一样, 仅遍历一遍, 但既然是求最长回文串, 那么长度不需要回退, 记录下当前最长的半径长度, 在遍历下一个字符时,(重点 1)直接套用最长半径, 然后判断半径内的字符是否对称, 然后从最长半径开始增长 (重点 2) 如果从中心点开始扩张, 那会走很多弯路, 因为绝大部分情况下, 是无法扩张到最长半径的, 因此, 从最长半径往中心点开始检测, 在数据量足够大或者字符类型足够多时, 非回文串的相同的概率越低, 效果越显著, 下图是 60 个随机 ascii 字符的运行时间, 单位 s
- class Solution(object):
- def longestPalindrome(self, s):
- len_longest = 0
- left = 0
- right = 0
- radius = 0
- if 1 == len(s) or 0 == len(s):
- return s
- temp_symmetry = [s[0], s[1]]
- len_s = len(s)
- for i in range(len_s):
- if i + 1 <len_s:
- if s[i] == s[i + 1]:
- [temp_left, temp_right, temp_len, temp_radius] = self.handle(s, i, i + 1, radius)
- if temp_len> len_longest:
- len_longest = temp_len
- left = temp_left
- right = temp_right
- radius = temp_radius
- if i>= 2:
- if temp_symmetry[0] == s[i]:
- [temp_left, temp_right, temp_len, temp_radius] = self.handle(s, i - 1, i - 1, radius)
- if temp_len> len_longest:
- len_longest = temp_len
- left = temp_left
- right = temp_right
- radius = temp_radius
- temp_symmetry.pop(0)
- temp_symmetry.append(s[i])
- # print(left)
- # print(right)
- print(radius)
- return s[left:right + 1]
- def handle(self, s, left, right, radius):
- right = right + radius
- left = left - radius
- len_left = left
- len_right = len(s) - right - 1
- if len_left < 0 or len_right < 0:
- return [-1, -1, -1, -1]
- for i in range(0, radius + 1):
- if s[left + i] != s[right - i]:
- return [-1, -1, -1, -1]
- if 0 == len_left and 0 == len_right:
- return [left, right, right - left + 1, radius]
- len_min = min(len_left, len_right)
- ori_left = left
- ori_right = right
- for i in range(1, len_min + 1):
- if s[ori_left - i] == s[ori_right + i]:
- left -= 1
- right += 1
- radius += 1
- else:
- break
- return [left, right, right - left + 1, radius]
来源: http://www.bubuko.com/infodetail-3415439.html