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

动态规划。

while True:
    try:
        s1, s2 = input(), input()
        if len(s1) > len(s2):
            s1, s2 = s2, s1
        m, n = len(s1), len(s2)
        dp = [0] * (n+1)
        max_lens = 0
        idx = 0
        a, b = 0, 0
        # print(m, n)
        for i in range(1, m + 1):
            for j in range(n, 0, -1):
                if s1[i-1] == s2[j-1]:
                    dp[j] = dp[j-1] + 1
                    if dp[j] > max_lens:
                        max_lens = dp[j]
                        idx = j
                else:
                    dp[j] = 0
        print(s2[idx - max_lens : idx])
    except:
        break