假设有两个字符串(可能包含空格),找出其中最长的公共连续子串,并输出其长度。
时间: 2023-04-25 11:00:58 浏览: 55
可以使用动态规划来解决这个问题。假设有两个字符串s1和s2,分别为长度为m和n。定义一个二维数组dp,其中dp[i][j]表示以s1[i-1]和s2[j-1]结尾的最长公共连续子串的长度。则有以下状态转移方程:
当s1[i-1] == s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1;
当s1[i-1] != s2[j-1]时,dp[i][j] = 。
最终的答案即为dp数组中的最大值。
具体实现可以参考以下代码:
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[] * (n+1) for _ in range(m+1)]
max_len =
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
else:
dp[i][j] =
return max_len
s1 = input("请输入第一个字符串:")
s2 = input("请输入第二个字符串:")
print("最长公共连续子串的长度为:", longest_common_substring(s1, s2))