[2020.1.15]最长回文子串(马拉车算法)

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

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

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

code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        # babad 预处理成：
            #        #b#a#b#a#d#
            #下标：  012345678910

        t = list(s)
        new_s = '#'+ '#'.join(t) + '#'

        # 用于记录答案
        res_start = 0
        res_len = 0

        # mx是目前遇到的回文串到达的最右的位置
        # mx_center是该回文串的中心
        mx_center = mx = 0

        # p[i]指 以i为中心的new_s中回文串的长度   原回文串长度为p[i]-1    （new_s恢复原字符： new_s[i]  = s[i//2]
        p = [0] * len(new_s)

        for i in range(1,len(new_s)-1):
            # 这句是马拉车算法的精髓，充分利用了已经检查过的字符（kmp算法也是这个思想）
            p[i] = min(mx-i,p[mx_center-(i-mx_center)]) if mx>i else 1
            # 检查i的时候，如果mx>i，那么由于i对应回文串在mx对应回文串内，与2mx_center-i 对应的回文对称
            # 考虑到2mx_center-i 对应的回文串可能最左边的一部分不在mx_center的对应的回文内，所以有了min(mx-i,p[mx_center-(i-mx_center)])

            # 在mx之右可能还有回文的一部分
            # （这里的边界判断i-p[i] >= 0 and i+p[i] < len(new_s)真的很恶心
            while i-p[i] >= 0 and i+p[i] < len(new_s) and  new_s[i-p[i]] == new_s[i+p[i]]:
                p[i] += 1

            # 更新最右的回文
            if p[i]+i>mx_center+p[mx_center] :
                mx_center = i
                mx = i+p[i]

            # 记录答案
            if res_len<p[i]:
                res_start = (i - p[i]+ 1) // 2
                res_len = p[i]

        return s[res_start:res_start+res_len-1]

吐槽

泰难了这个，跟kmp一样，算法是很牛逼，但是没有通用的思想，下次还是写不出来（除非硬背）

djtu-zcx / algrothm

[2020.1.15]最长回文子串(马拉车算法) #45

题目

code

吐槽