给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。所谓回文串,指左右对称的字符串。
时间复杂度: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)