Python 最长公共子串,题目描述：a b两个字符串，求a b的最长公共子串，输出最长公共子串长度和最长公共子串，当有多个等长的最长公共子串，输出在a中出现的第一个子串。子串与子序列不同，子串必须是连续的，而子序列可以不连续。 【输入形式】 分两行输入两个字符串 【输出形式】 一行输出长度

和最长公共子串，用空格隔开。

【样例输入】

abcd1234

bcdabcd12

【样例输出】

4 bcd1

【Python代码】

def longest_common_substring(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len, end = 0, 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end = i
else:
dp[i][j] = 0
return max_len, a[end - max_len:end]

a = input().strip()
b = input().strip()
print(*longest_common_substring(a, b))

相关问题

最长公共子串,题目描述：a b两个字符串，求a b的最长公共子串长度，输出最长公共子串长度。子串与子序列不同，子串必须是连续的，而子序列可以不连续。求python代码

好的，以下是Python代码实现：

def longest_common_substring(a, b):
    m, n = len(a), len(b)
    # 初始化dp数组
    dp = [[0] * (n+1) for _ in range(m+1)]
    # 初始化最长公共子串长度
    max_len = 0
    # 遍历a和b的每个字符
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])
            else:
                dp[i][j] = 0
    # 返回最长公共子串长度
    return max_len

其中，a和b分别表示输入的两个字符串。使用双重循环遍历a和b的每个字符，并根据定义的dp数组进行动态规划。最后返回最长公共子串长度即可。

最长公共子串,题目描述: a b两个字符串，求ab的最长公共子串长度，输出最长公共子串长度。子串与子序列不同，子串必须是连续的，而子序列可以不连续。用python

好的，这道题目可以使用动态规划的思想，具体实现如下：

a = input()  # 读入字符串a
b = input()  # 读入字符串b

# 初始化动态规划矩阵
dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]
max_len = 0  # 记录最长公共子串长度

# 动态规划
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1]:  # 如果当前字符相同
            dp[i][j] = dp[i-1][j-1] + 1
            max_len = max(max_len, dp[i][j])  # 更新最长公共子串长度
        else:  # 如果当前字符不同
            dp[i][j] = 0

print(max_len)  # 输出最长公共子串长度

以上代码实现了读入字符串a和字符串b，求它们的最长公共子串长度，并输出最长公共子串长度。