【打卡贴】（No.005）从零开始刷LeetCode

输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。

输入: "cbbd"输出: "bb"

        l = len(s)
        max_length = 0
        p = ''
        if len(s) == 1:
            return s
        for i in range(l):
            for j in range(i + 1, l):
                is_p = True
                for k in range(i, int((i + j) / 2) + 1):
                    if s[k] != s[j - k + i]:
                        is_p = False
                        break
                if is_p and (j - i + 1) > max_length:
                    max_length = j - i + 1
                    p = s[i:j + 1]
        if p == '':
            p = s[0]
        return p

# manacher算法
def manacher(self):
        # 字符串处理，
     # 用特殊字符隔离字符串方便处理偶数子串
        s = '#' + '#'.join(self.string) + '#'
        lens = len(s)
        # 辅助列表：
        # f[i]表示i作中心的最长回文子串的长度
        f = []
        # 记录对i右边影响最大的字符位置j
        maxj = 0
        # 记录j影响范围的右边界
        maxl = 0
        # 记录最长的回文子串长度
        maxd = 0
        # 遍历字符串
        for i in range(lens):
            if maxl > i:
            # 这里为了方便后续计算使用count，
        # 其表示当前字符到
        #其影响范围的右边界的距离
            count = min(maxl-i, int(f[2*maxj-i]/2)+1)
            else :
                count = 1
                # 两边扩展
            while i-count >= 0 and i+count \
                   < lens and s[i-count] == s[i+count]:
                count += 1
               # 更新影响范围最大的字符j及其右边界
            if(i-1+count) > maxl:
                maxl, maxj = i-1+count, i
            f.append(count*2-1)
            # 更新回文子串最长长度
            maxd = max(maxd, f[i])
            # 去除特殊字符
        return int((maxd+1)/2)-1