题解 | #公共子串计算#

动态规划解

1. 创建dp增广矩阵
2. 演算推理动态规划递推关系式

while True:
    try:
        s1, s2, ans = input(), input(), 0
        dp = [[0 for i in s1+'0'] for j in s2+'0']
        for j in range(len(s1)):
            for i in range(len(s2)):
                if s1[j] == s2[i]:
                    dp[i+1][j+1] = dp[i][j] + 1
                if dp[i+1][j+1] > ans:
                    ans = dp[i+1][j+1]
        print(ans)
    except EOFError:
        break