HJ75 公共子串计算

本节目标：理解“HJ75 公共子串计算”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：36.30% 时间限制：1秒 空间限制：32M 知识点 ==字符串====查找====动态规划== 描述 给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。 数据范围：字符串长度：0 1≤s≤150 进阶：时间复杂度：O(_n_3) ，空间复杂度： O(n) 输入描述： 输入两个只包含小写字母的字符串 输出描述： 输出一个整数，代表最大公共子串的长度 示例1 输入： asdfaswerasdfaswer ==复制== 输出： 6 ==复制==

为了解决这个问题，我们可以使用动态规划的方法。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

这个问题中，我们定义一个二维数组dp，其中dp[i][j]代表以第一个字符串中第i个字符结尾和第二个字符串中第j个字符结尾的最大公共子串的长度。初始时，dp[i][j]都为0。

然后，我们遍历两个字符串，当发现两个字符相同时，我们就更新dp[i][j]为dp[i-1][j-1] + 1，即在之前最大公共子串长度的基础上加1。如果字符不相同，则dp[i][j]保持为0，因为以这两个字符结尾的子串不可能是公共子串。

遍历完成后，数组dp中的最大值即为最大公共子串的长度。

下面是Python代码实现： def max_common_substring_length(str1, str2): n = len(str1) m = len(str2) dp = [[0] * (m + 1) for _ in range(n + 1)] max_length = 0 for i in range(1, n + 1): for j in range(1, m + 1): if str1[i - 1] == str2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 max_length = max(max_length, dp[i][j]) return max_length

测试代码

str1 = "asdfas" str2 = "werasdfaswer" print(max_common_substring_length(str1, str2))

这段代码定义了一个函数max_common_substring_length，它接收两个字符串作为参数，计算它们的最大公共子串的长度，并返回这个长度。这个实现的时间复杂度为O(n*m)，空间复杂度为O(n*m)，其中n和m分别是输入字符串的长度。