美文网首页
最长回文子串

最长回文子串

作者: 雨_树 | 来源:发表于2017-05-02 12:48 被阅读32次

    给定一个字符串,求它的最长会问子串的长度

    方法一:中心扩展

    依次遍历字符串,向两边查找回文,在查找时要注意偶数回文和奇数回文得分别判断。因为有两层循环,时间复杂度为O(n^2)

    方法二:Manacher算法

    有趣的算法,针对方法一中的“奇偶数回文”和“重复访问”的问题改进,复杂度为线性O(n)。

    算法详情可以参见https://segmentfault.com/a/1190000003914228

    相关文章

      网友评论

          本文标题:最长回文子串

          本文链接:https://www.haomeiwen.com/subject/mtuctxtx.html