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

import sys

# 读取两个输入字符串
s = input()  # 第一个字符串
t = input()  # 第二个字符串

# 初始化存储公共子串长度和内容的列表
string_len_list = []  # 存储所有公共子串的长度
string_list = []      # 存储所有公共子串的内容

# 判断哪个字符串更短，就以它为基准寻找公共子串，来尽可能的减小一些时间复杂度
if len(s) >= len(t):
    # 遍历较短的字符串t的所有可能的子串
    for i in range(len(t)):          # 子串起始位置
        for j in range(i, len(t)):   # 子串结束位置
            # 检查t[i:j+1]是否是s的子串
            if t[i:j+1] in s:
                string_len = j - i + 1  # 计算子串长度
                string = t[i:j+1]       # 获取子串内容
                string_len_list.append(string_len)
                string_list.append(string)
else:
    # 同上，但以s为基准寻找公共子串
    for i in range(len(s)):
        for j in range(i, len(s)):
            if s[i:j+1] in t:
                string_len = j - i + 1
                string = s[i:j+1]
                string_len_list.append(string_len)
                string_list.append(string)

# 找出最大的公共子串长度
max_len = max(string_len_list)

# 遍历所有公共子串，找到第一个长度等于max_len的子串并输出
for k in range(len(string_len_list)):
    if string_len_list[k] == max_len:
        print(string_list[k])  # 输出最长公共子串
        break                  # 找到第一个就退出循环