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

# Process input
s = input()
t = input()
if len(s) > len(t):
    s, t = t, s

# DP
arrRow_1 = [0] * (len(t) + 1)
maxLen = 0
resStartT = 0
for i in range(len(s)):
    chS = s[i]
    for j in range(len(t)-1, -1, -1):
        chT = t[j]
        if chS == chT:
            curLen = arrRow_1[j] + 1
            arrRow_1[j+1] = curLen
            if curLen > maxLen:
                maxLen = curLen
                resStartT = j - curLen + 1
        else:
            arrRow_1[j+1] = 0

# Output
res = t[resStartT: resStartT+maxLen]
print(res)