题解 | 查找两个字符串a,b中的最长公共子串
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
# 最长公共子串（连续）
# LCS 是不连续的 二维动态规划
text1 = input()
text2 = input()
# abcdefghijklmnop
# abcsafjklmnopqrstuvw
# 动态规划
if len(text1) > len(text2): # 让text1为较短的，
text1, text2 = text2, text1
rows, cols = len(text1), len(text2)
dp = [[0] * cols for _ in range(rows)] # dp[i][j]代表以i,j结尾的最长公共子串
for r in range(rows):
if text2[0] == text1[r]:
dp[r][0] = 1
for c in range(cols):
if text1[0] == text2[c]:
dp[0][c] = 1
for r in range(1, rows):
for c in range(1, cols):
if text1[r] == text2[c]:
dp[r][c] = dp[r - 1][c - 1] + 1
max_r = 0
longest = 0
for i, r in enumerate(dp):
t = max(r)
if t > longest:
longest = t
max_r = i
print(text1[max_r - longest + 1:max_r + 1])
和LCS很像，只不过子串是连续的，可以使用动态规划，只要令dp[i][j]为以text1[i]、text2[j]结尾的最长子串就行
