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

import sys

#输入
n1 , m1 = input() , input()
#初始化
if len(n1) > len(m1):
    s = n1
    n1 = m1
    m1 = s
n = len(n1)
m = len(m1)

#数组
dp = [[0]*m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if n1[i] == m1[j]:
            dp[i][j] = 1

#找到最长字串的长度
for i in range(1,n):
    for j in range(1,m):
        if dp[i][j] == 1:
            dp[i][j] += dp[i-1][j-1]

#找到下标并输出
ans, mm  = 0, 0
for i in range(n):
    if max(dp[i]) > ans:
        mm = i
        ans = max(dp[i])
print(n1[mm-ans+1:mm+1])