题解 | 查找两个字符串a,b中的最长公共子串

# 最长公共子串（连续）
# 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]结尾的最长子串就行