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

s1 = input()  # 短字符串
s2 = input()  # 长字符串

# 交换字符保证s1是短字符串
if len(s1) > len(s2):
    s1, s2 = s2, s1

# 求子串
def get_substring(s):

    sub = set()  # 子串

    for i in range(len(s)):  # 子串的开始位置
        for j in range(i + 1, len(s) + 1):  # 子串的结束位置
            sub.add(s[i:j])
    return sub


# 集合操作，交集是公共子串
sub1 = get_substring(s1)
sub2 = get_substring(s2)
public_sub = sub1.intersection(sub2)

# 最长公共子串
max_long = max(len(ele) for ele in public_sub)
max_public_sub = [sub for sub in public_sub if len(sub) == max_long]

# 最长公共子串在s1总的索引
index_sub = {}

for sub in max_public_sub:
    ind = s1.find(sub)
    index_sub[ind] = sub

# 输出索引值最小的子串
min_key = min(index_sub)
print(index_sub[min_key])