(1)ebebaabe 的最长回文子串是
(2)以下函数用于获取某字符串中最长的回文子串,请补全代码。
def longestPalindrome(s):
def expandAroundCenter(s, left, right):
while ①
left -= 1
right += 1
return left + 1, right – 1
start, end = 0, 0
for i in range(len(s)):
left1, right1 = expandAroundCenter(s, i, i)
left2, right2 = ②
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return ③
(3)在实际应用中以上算法在处理较长字符串时效率过于低下。我们若利用回文串的对称性减少字符的访问次数可以大幅度提升该算法的效率。以下是一种实现。请补全代码。
def longestPalindrome(s):
end, start = -1, 0
s = '/' + '/'.join(list(s)) + '/' #处理偶数长度的子串
arm_len = []
right = j= -1
def get_arm_len(s, left, right):
left_idx, right_idx = expand_around_center(s, left, right)
return (right_idx - left_idx) // 2
for i in range(len(s)):
if right >= i:
i_sym = 2 * j - i
min_arm_len = min(arm_len[i_sym], right - i)
cur_arm_len = ①
else:
cur_arm_len = get_arm_len(s, i, i)
②
if ③
j = i
right = i + cur_arm_len
if 2 * cur_arm_len + 1 > end - start:
start = i - cur_arm_len
end = i + cur_arm_len
return ④

同类型试题

y = sin x, x∈R, y∈[–1,1],周期为2π,函数图像以 x = (π/2) + kπ 为对称轴
y = arcsin x, x∈[–1,1], y∈[–π/2,π/2]
sin x = 0 ←→ arcsin x = 0
sin x = 1/2 ←→ arcsin x = π/6
sin x = √2/2 ←→ arcsin x = π/4
sin x = 1 ←→ arcsin x = π/2


y = sin x, x∈R, y∈[–1,1],周期为2π,函数图像以 x = (π/2) + kπ 为对称轴
y = arcsin x, x∈[–1,1], y∈[–π/2,π/2]
sin x = 0 ←→ arcsin x = 0
sin x = 1/2 ←→ arcsin x = π/6
sin x = √2/2 ←→ arcsin x = π/4
sin x = 1 ←→ arcsin x = π/2

