题解 | #公共子串计算# Python3 DP

DP解法，时间复杂度O(MN):

def dp(s1, s2):
    m, n = len(s1) + 1, len(s2) + 1
    li = [[0] * m for _ in range(n)]
    max_len = 0
    for row in range(1, n):
        for col in range(1, m):
            if s1[col - 1] == s2[row - 1]:
                if li[row - 1][col - 1]:
                    li[row][col] = li[row - 1][col - 1] + 1
                else:
                    li[row][col] = 1
                max_len = max(max_len, li[row][col])
    return max_len


if __name__ == '__main__':
    while True:
        try:
            a = input()
            b = input()
            print(dp(a, b))
        except:
            break

关键在于构造DP表：

当DP表的行和列对应的字符相等时，需要对应位置记录为1，如果li[i-1][j-1]为非0，说明是连续字符串，需要加上li[i-1][j-1]的值。