大脑康复训练 | 马拉车算法 python实现

        s = list(s)
        s = "\0#"+"#".join(s) +"#\1"
        def manacher(sss):
            mx = -1
            id0 = -1
            length = len(sss)
            p = [0]*length
            maxstr = ""
            for i in range(1,length-1):
                if i < mx:
                    j = 2*id0 - i
                    p[i] = min(p[j],mx-i)
                while sss[i-p[i]-1] == sss[i+p[i]+1]:
                    p[i]+=1
                if p[i]+i > mx:
                    mx = p[i]+i
                    id0 = i
                if len(maxstr) < 2*p[i]+1:
                    maxstr = sss[i-p[i]:i+p[i]+1]
            return maxstr
        return manacher(s).replace("#","")