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

• 状态转移方程
• a[i] == b[i], dp[i][j] = dp[i-1][j-1]，dp表示以a[i]结尾的字串和以b[j]结尾的字串的最长公共子串

a = input()
b = input()

# 确保a就是较短串
if len(a) > len(b):
    a, b = b, a

# 初始化
n, m = len(a) + 1, len(b) + 1
dp = [[0] * m for _ in range(n)]

max_n = 0
idx = -1
for i in range(1, n, 1):
    for j in range(1, m, 1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        if dp[i][j] > max_n:
            max_n = dp[i][j]
            # dp[i][j]表示的是下标为i-1,j-1的两个字串
            idx = i-1

print(a[idx - max_n + 1 : idx + 1] if idx != -1 else "")