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

python的max()对二维数组的行为是：按照字典序返回最大值，而不是每一行返回一个最大值=-=。哎。

s = input()
t = input()

if len(t) > len(s):
    s, t = t, s

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]

for i in range(1, len(t)+1):
    for j in range(1, len(s)+1):
        if t[i-1] == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = 0

max_values = []
for each_line in dp:
    max_values.append(max(each_line))
max_value = max(max_values)
for i in range(1, len(t)+1):
    for j in range(1, len(s)+1):
        if dp[i][j] == max_value:
            break
    else:
        continue
    break
print(t[i-max_value:i])