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

#用动态规划来解
#
while True:
    try:
        s1 = input()
        s2 = input()
        m = len(s1)
        n = len(s2)
        #使s1为最短长度字符串，在搜索过程后，处于外循环，可以先匹配到最前的子串。应对相等长度子串要求输出短串中最先出现的要求。
        if m > n :
            temp = s1
            s1 = s2
            s2 = temp
        m = len(s1)
        n = len(s2)
        
        max_len = 0 # 记录最长子串长度
        max_loc = [0, 0] #记录最长子串的尾部位置
        dp = [[0 for j in range(n+1)] for i in range(m+1)] #初始化dp table
        #dp 的值定义为以当前位置字符结尾的公共子串长度
        for i in range(1, m+1): # 
            for j in range(1, n+1): #先搜索长串
                if s1[i-1] == s2[j-1]: #如果当前两字符相等，则长度为前子串长度+1
                    dp[i][j] = dp[i-1][j-1] +1
                    if dp[i][j] > max_len:  #判断子串长度是否比记录到的更长，是则更新最长值，且更新尾部位置
                        max_len = dp[i][j]
                        max_loc = [i, j]
                else: #如果当前两字符不相等，则不存在公共子串，即=0
                    dp[i][j] = 0
        print(s1[max_loc[0]-max_len:max_loc[0]])
    except:
        break