题解 | 查找两个字符串a,b中的最长公共子串 | Python DP O(m*n)

s, t = input(), input()

# DP
# 阶段：s前i个字符，t前j个字符
# 状态：以s(i)、t(j)结尾的公共子串长度
if len(s) > len(t): s, t = t, s
m, n = len(s)+1, len(t)+1
dp = [0] * n
maxLen, resEndI = 0, 0
for i in range(1, m):
    chs = s[i-1]
    for j in range(n-1, 0, -1):
        cht = t[j-1]
        if cht == chs:
            dp[j] = curLen = dp[j-1] + 1
            if curLen > maxLen:
                maxLen = curLen
                resEndI = i
        else:
            dp[j] = 0

# Output
print(s[resEndI-maxLen: resEndI])