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

import sys
s, t = input(), input()
if len(s)<len(t):
    s, t = t, s
s_n, t_n = len(s), len(t)

dp = [[0] * (t_n+1) for _ in range(s_n+1)]
# print(s, t)
max_v, max_i, max_j = 0, -1, -1
for i in range(1, s_n+1):
    for j in range(1, t_n+1):
        dp[i][j] = dp[i-1][j-1] + 1 if s[i-1]==t[j-1] else 0
        if dp[i][j] > max_v:
            max_v, max_i, max_j = dp[i][j], i-1, j-1
        elif dp[i][j] == max_v and (j-1) < max_j:
            max_i, max_j = i-1, j-1# s作为行，保证最短的第一次搜索到
# print(max_v, max_i, max_j)
print(s[(max_i - max_v+1):(max_i+1)])

遇到最长最短，首选动态规划。其中输出结果要求最短串中最先出现，因此在判断时需要额外条件更新子串的索引。