给你一个字符串 s,找到 s 中最长的回文子串。
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
这里只以手绘小图片的方式简单讲解「Manacher 算法」
这个小人以身体为轴,左右对称,可以看作一个回文字符串(设想所有字符分布在其手臂和脖子上)。也就是以脖子为中心,左右对称。
脖子上的字符对应的臂长就是当前手臂的长度。
思考如何利用回文串的对称性,快速得出 a
的最小臂长,也就是当 a
为脖子时,它的手臂至少是多长。
………. 思考中 ………
在此图中的情况下,a
的臂长至少至少等于 a'
的臂长。只需要在这个臂长的基础上计算其臂长是否更大。
计算方法就是不断让自己的手臂延长,检查变成之后左右两手是否还相等
这个情况下,a
的基础臂长是 a'
到脖子的距离
图片是在 https://sketch.io/sketchpad/ 随手画的
手机扫一扫
移动阅读更方便
你可能感兴趣的文章