最长回文子串
2017-05-02 本文已影响32人
雨_树
给定一个字符串，求它的最长会问子串的长度
方法一：中心扩展
依次遍历字符串，向两边查找回文，在查找时要注意偶数回文和奇数回文得分别判断。因为有两层循环，时间复杂度为O(n^2)
方法二：Manacher算法
有趣的算法，针对方法一中的“奇偶数回文”和“重复访问”的问题改进，复杂度为线性O(n)。
算法详情可以参见https://segmentfault.com/a/1190000003914228
给定一个字符串，求它的最长会问子串的长度
方法一：中心扩展
依次遍历字符串，向两边查找回文，在查找时要注意偶数回文和奇数回文得分别判断。因为有两层循环，时间复杂度为O(n^2)
方法二：Manacher算法
有趣的算法，针对方法一中的“奇偶数回文”和“重复访问”的问题改进，复杂度为线性O(n)。
算法详情可以参见https://segmentfault.com/a/1190000003914228
