[MathJax]/localization/zh-hans/MathMenu.js加载中
学进去-教育应平等而普惠
试题
类型:操作题
难度系数:0.65
所属科目:高中信息技术
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。现给出一个字符串 ,设计程序搜索其中最长的回文子串。
(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

用户名称
2019-09-19

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

用户名称
2019-09-19
我要答疑
编写解析
解析:

奖学金将在审核通过后自动发放到帐

提交
我要答疑
我要答疑:
提交