当前位置: 首页> 房产> 政策 > 微信小程序开发视频完整教程_360免费创建个人网站_网络优化行业的发展前景_2023年5月疫情爆发

微信小程序开发视频完整教程_360免费创建个人网站_网络优化行业的发展前景_2023年5月疫情爆发

时间:2025/7/11 8:32:56来源:https://blog.csdn.net/weixin_51652691/article/details/144096549 浏览次数:0次
微信小程序开发视频完整教程_360免费创建个人网站_网络优化行业的发展前景_2023年5月疫情爆发

给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。所谓回文串,指左右对称的字符串。

时间复杂度:O(n2)  ,空间复杂度:O(1) 

import sys
def longest_substring_length(s):n = len(s)if n == 0:return 0def expand_around_center(left, right):while left >= 0 and right < n and s[left] == s[right]:left -= 1right += 1return right - left - 1      max_len = 1  # 最小的回文子串长度为1   for i in range(n):# 以单个字符为中心扩展len1 = expand_around_center(i, i)# 以两个字符之间为中心扩展len2 = expand_around_center(i, i + 1)max_len = max(max_len, len1, len2)return max_len
for line in sys.stdin:s = line.split()[0]n = longest_palindromic_substring_length(s)print(n)

优化:时间复杂度:O(n) ,空间复杂度:O(n) 

import sys
def longest_palindromic_substring_length(s):t = "#" + "#".join(s) +"#"n = len(t)if n <= 2:return 0p = [0] * n  # p[i]表示以t[i]为中心的回文半径center, right = 0, 0for i in range(n):if i < right:p[i] = min(right - i, p[2*center - i])while i +p[i] +1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:p[i] += 1if i + p[i] > right:center, right = i, i+p[i]max_len = max(p)return max_len
for line in sys.stdin:s = line.split()[0]n = longest_palindromic_substring_length(s)print(n)

关键字:微信小程序开发视频完整教程_360免费创建个人网站_网络优化行业的发展前景_2023年5月疫情爆发

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: