微信小程序开发视频完整教程_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)