题解 | 公共子串计算 | Python DP O(m*n)

s, t = input(), input()

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

print(maxLen)