给定2个字符串，试求出这2个字符串的最长公共子串的长度。 输入格式: 输入共2行，每行一个字符串。字符均为小写英文字母。 输出格式: 仅一行，包含一个正整数，表示2个字符串的最长公共子串长度。对于30%的数据，保证字符串长度不超过10； 对于60%的数据，保证字符串长度不超过100； 对于90%的数据，保证字符串长度不超过1000； 对于100%的数据，保证字符串长度不超过5000；代码怎么写

本题可以使用动态规划来解决，定义状态dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串长度。则有以下状态转移方程：

if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = 0

其中，s1和s2分别表示两个字符串。

最终结果即为所有dp[i][j]中的最大值。

以下是完整Python代码实现：

相关问题

给定2个字符串，试求出这2个字符串的最长公共子串的长度。 输入格式: 输入共2行，每行一个字符串。字符均为小写英文字母。 输出格式: 仅一行，包含一个正整数，表示2个字符串的最长公共子串长度。对于30%的数据，保证字符串长度不超过10； 对于60%的数据，保证字符串长度不超过100； 对于90%的数据，保证字符串长度不超过1000； 对于100%的数据，保证字符串长度不超过5000；

可以使用动态规划来解决这个问题。

假设第一个字符串为s1，第二个字符串为s2，令dp[i][j]表示以s1[i]和s2[j]为结尾的最长公共子串的长度。则有以下状态转移方程：

- 如果s1[i] == s2[j]，那么dp[i][j] = dp[i-1][j-1] + 1；
- 如果s1[i] != s2[j]，那么dp[i][j] = 0。

最终的结果就是dp数组中的最大值。

代码如下：

最长公共子串的长度 描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度（假设str1和str2的最长公共子串存在且唯一）。 输入样例： 1AB2345CD 12345EF 输出样例： 4 说明：最长的公共子串为2345；

可以使用动态规划来解决该问题。定义一个二维数组dp，其中dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子串的长度。则当str1[i-1]和str2[j-1]相同时，dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=0。最后，遍历dp数组找到最大值即可。

Python代码实现如下：

def longest_common_substring(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

# 示例
str1 = "1AB2345CD"
str2 = "12345EF"
print(longest_common_substring(str1, str2))  # 输出 4