2018-03-21 最长回文子串搜索

(1)暴力解法

遍历字符串中所有的子串,然后对每个子串进行回文检测。时间复杂度O(n的三次方)

(2)对称性质改进

遍历所有子串改为遍历所有子串的中心点,向外扩散,从左自右,受到边界和对称性的影响,当长度达到一定时,达到边界,可不用再继续往外扩散探索。而整个字符串的字符以及字符间的空隙都有可能是这个中心点。只要遍历所有这些中心点,在向外扩散的同时,一边注意左右字符是否对称,一边注意是否达到最大边界即可。长度为n的字符串的中心点有2n-1个。每个中心点的平均比较次数为n/4(最长比较长度为n/2)。总得算法时间复杂度为O(n的平方)。

(3)马拉车算法

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串,求它的最长回文子串长度...
    林大鹏阅读 2,804评论 0 6
  • 问题定义 最长回文子串问题:给定一个字符串,求它的最长回文子串长度。 解法1:暴力解法 找到字符串的所有子串,判断...
    HITMiner阅读 721评论 0 2
  • 你说,我给你讲个故事,有个女孩开玩笑给一个男孩起了个外号,结果那个男孩用了一辈子。------题记 2015年冬天...
    陈小咩_Kiki阅读 374评论 0 0
  • 01 忽然之间,2016年已经过半。 翻开2016年的新年计划,我上半年制定的目标基本上都实现了。 当然也有目标,...
    杨小米阅读 3,174评论 15 98
  • 介绍SiriKit SiriKit是让你的内容通过Siri展示的一个框架库。当用户向Siri请求特别类型的服务时,...
    孢子菌阅读 4,386评论 1 6