即墨网站建设招聘,企业类网站有哪些,中铁广州建设有限公司网站,网站开发的课程设置哈喽大家好#xff0c;周二也是令人愉快的一天啊#xff0c;今天天气不错#xff0c;坐在窗户旁边边晒太阳边写文章#xff0c;再泡杯热茶#xff0c;真是舒服美好#xff0c;废话不多说#xff0c;今天说一下Python求最长子串长度#xff0c;希望对大家有作用#xf…哈喽大家好周二也是令人愉快的一天啊今天天气不错坐在窗户旁边边晒太阳边写文章再泡杯热茶真是舒服美好废话不多说今天说一下Python求最长子串长度希望对大家有作用raksmart服务器。给定一个字符串求它最长的回文子串长度例如输入字符串35534321它的最长回文子串是3553所以返回4。最容易想到的办法是枚举出所有的子串然后一一判断是否为回文串返回最长的回文子串长度。不用我说枚举实现的耗时是我们无法忍受的。那么有没有高效查找回文子串的方法呢答案当然是肯定的那就是中心扩展法选择一个元素作为中心然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题回文子串的长度即可能是基数也可能好是偶数对于长度为偶数的回文子串来说是不存在中心元素的。那是否有一种办法能将奇偶长度的子串归为一类统一使用中心扩展法呢它就是manacher算法在原字符串中插入特殊字符例如插入#后原字符串变成#3#5#5#3#4#3#2#1#。现在我们对新字符串使用中心扩展发即可中心扩展法得到的半径就是子串的长度。现在实现思路已经明确了先转化字符串35534321 ---- #3#5#5#3#4#3#2#1#然后求出以每个元素为中心的最长回文子串的长度。以下给出Python实现:功能已经实现了经过测试也没有bug但是我们静下心来想一想目前的解法是否还有优化空间呢根据目前的解法我们求出了‘35534321‘中每个元素中心的最大回文子串。当遍历到4时我们已经知道目前最长的回文子串的长度max_length是4这是我们求出了以4为中心的最长回文子串长度是3它比max_length要小所以我们不更新max_length。换句话说我们计算以4为中心的最长回文字串长度是做了无用功。这就是我们要优化的地方既然某个元素的最长的回文子串长度并没有超过max_length我们就没有必要计算它的最长回文子串在遍历一个新的元素时我们要优先判断以它为中心的回文子串的长度是否能超越max_length如果不能超过就继续遍历下一个元素。以下是优化后的实现#!/usr/bin/python# -*- coding: utf-8 -*-def max_substr(string):s_list [s for s in string]string # #.join(s_list) #max_length 0length len(string)for index in range(0, length):r_length get_length2(string, index, max_length)if max_lengthmax_length r_lengthreturn max_lengthdef get_length2(string, index, max_length):# 基于已知的最长字串求最长字串# 1.中心最大半径超出字符串范围, returnr_ len(string)if index max_length r_:return max_length# 2.无法超越最大半径, returnl_string string[index - max_length 1 : index 1]r_string string[index : index max_length]if l_string ! r_string[::-1]:return max_length# 3.计算新的最大半径result max_lengthfor i in range(max_length, r_):if index-i 0 and indexiresult 1else:breakreturn result - 1if __name__ __main__:result max_substr(35534321)print result那么速度到底提升了多少呢以字符串1000个‘1’为例优化前的算法执行时间为0.239018201828优化后为0.0180191993713速度提升了10倍左右/usr/bin/python /Users/hakuippei/PycharmProjects/untitled/the_method_of_programming.py怎么样是不是很好用呢今天就到这里大家明天见咯。
