题解 | #查找两个字符串a,b中的最长公共子串#经典动态规划

while True:

try:
    str_input1, str_input2 = input(), input()
    # 区分一下字符串长短
    str1 = str_input1 if len(str_input1) <= len(str_input2) else str_input2
    str2 = str_input2 if len(str_input1) <= len(str_input2) else str_input1
    
    m = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
    
    # 最长子串的长度
    max_sub_len = 0
    # 最长子串最后一个字符在str1中的索引位置
    p = 0
    
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                m[i+1][j+1] = m[i][j] + 1
                if m[i+1][j+1] > max_sub_len:
                    max_sub_len = m[i+1][j+1]
                    p = i
    print(str1[p + 1 - max_sub_len: p + 1])

except:
    break