HJ32 密码截取

本节目标：理解“HJ32 密码截取”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：28.15% 时间限制：1秒 空间限制：32M 知识点 ==字符串====动态规划== 描述 Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？ 数据范围：字符串长度满足 1≤n≤2500 输入描述： 输入一个字符串（字符串的长度不超过2500） 输出描述： 返回有效密码串的最大长度 示例1 输入： ABBA 输出： 4 示例2 输入： ABBBA 输出： 5 示例3 输入： 12HHHHA 输出： 4

解决这类问题的一种有效方法是使用动态规划来找到最长的回文子串。动态规划的基本思想是将问题分解成相关的子问题，然后结合子问题的解来生成原问题的解。

思路

定义一个二维数组 dp，其中 dp[i][j] 表示字符串从索引 i 到索引 j 的子串是否是回文串。如果是回文串，dp[i][j] = True，否则 dp[i][j] = False。

1. 初始化：对于任意字符串 s，长度为 1 的子串总是回文串，所以 dp[i][i] = True。长度为 2 的子串如果两个字符相同，则是回文串，所以如果 s[i] == s[i+1]，则 dp[i][i+1] = True。

2. 状态转移：对于长度大于 2 的子串，如果 s[i] == s[j] 且 dp[i+1][j-1] 是回文串，则 dp[i][j] 也是回文串。

3. 寻找最长回文子串：在填充 dp 数组的过程中记录最长回文子串的长度。

实现

def longest_palindrome(s): n = len(s) dp = [[False] * n for _ in range(n)] max_len = 0

从字符串的末尾开始向前遍历

for i in range(n-1, -1, -1): for j in range(i, n):

字符串从i到j的子串如果是回文

if s[i] == s[j] and (j - i < 3 or dp[i+1][j-1]): dp[i][j] = True max_len = max(max_len, j - i + 1) return max_len

输入字符串

s = input()

输出最长有效密码串的长度

print(longest_palindrome(s))

这段代码首先初始化了一个二维的布尔数组 dp 来记录子串是否是回文串。然后，通过双重循环遍历字符串的所有可能的子串，利用动态规划的方法更新 dp 数组的值。最后，返回找到的最长回文子串的长度。

要优化找到最长回文子串的算法，我们可以考虑使用 中心扩展法。这个方法的核心思想是：对于字符串中的每个字符（或字符对），尝试将其作为回文子串的中心，然后向两边扩展，直到不能形成更长的回文子串为止。

中心扩展法的优点是它不需要使用额外的空间来存储子问题的解，因此空间复杂度降低到 O(1)，而时间复杂度仍然是 O(n^2)，但在实践中通常比动态规划方法更快，因为它避免了不必要的计算。

实现步骤

1. 遍历字符串的每个字符，将每个字符或字符对作为回文中心。
2. 从中心向两边扩展，检查并更新最长回文子串的长度。
3. 注意处理两种情况：奇数长度的回文和偶数长度的回文。

代码示例

def longest_palindrome(s): def expand_around_center(left, right):

从中心向两边扩展

while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1

返回扩展后的回文子串的长度

return right - left - 1 start, end = 0, 0 for i in range(len(s)):

以 s[i] 为中心的最长回文子串

len1 = expand_around_center(i, i)

以 s[i] 和 s[i+1] 为中心的最长回文子串

len2 = expand_around_center(i, i + 1)

取两者之间的最大值

max_len = max(len1, len2) if max_len > end - start: start = i - (max_len - 1) // 2 end = i + max_len // 2 # 最长回文子串的长度 return end - start + 1

输入字符串

s = input()

输出最长有效密码串的长度

print(longest_palindrome(s)) 这段代码通过中心扩展法计算了给定字符串中最长回文子串的长度。expand_around_center 函数负责从给定的中心位置向两边扩展，寻找最长的回文子串，并返回其长度。然后，主函数遍历字符串的每个位置，分别考虑奇数长度和偶数长度的回文子串，最后返回找到的最长回文子串的长度。这种方法相比动态规划，虽然时间复杂度相同，但由于减少了冗余计算，通常执行速度更快，且空间复杂度更低。

奇数长度的回文和偶数长度的回文 在寻找最长回文子串的问题中，考虑两种长度的回文子串是必要的，因为回文子串可以是奇数长度也可以是偶数长度。这两种情况需要分别处理：

1. 奇数长度的回文子串：这种类型的回文以某个字符为中心，然后向两边扩展。例如，在字符串 "racecar" 中，以字符 'e' 为中心的最长回文子串是 "racecar" 本身。

2. 偶数长度的回文子串：这种类型的回文以某两个相邻字符之间的位置为中心，然后向两边扩展。例如，在字符串 "aabbaa" 中，以字符 'b' 和 'b' 之间为中心的最长回文子串是 "aabbaa" 本身。

为了涵盖这两种情况，我们需要分别检查以 s[i] 为中心的奇数长度回文子串（len1），和以 s[i] 与 s[i+1] 为中心的偶数长度回文子串（len2）。这样可以确保不遗漏任何可能的回文子串，无论其长度是奇数还是偶数。

expand_around_center 函数的作用是从中心向两边扩展，尝试找到最长的回文子串，并返回该回文子串的长度。对于奇数长度的回文，中心是一个字符；对于偶数长度的回文，中心是两个字符之间的空隙。这就是为什么要计算两个 len 的原因，以确保能够找到所有可能的回文子串，并从中选出最长的那一个。

这种方法相比动态规划有更好的时间复杂度，因为它避免了不必要的计算，直接从每个可能的中心点向外扩展寻找回文子串，时间复杂度为 O(n^2)，其中 n 是字符串的长度。尽管最坏情况下时间复杂度仍然是 O(n^2)，但在实际应用中，由于很多扩展很快就会停止，所以这种方法在实践中通常比动态规划要快。