如何在多字符串列表中查找最长公共子串？已尝试SequenceMatcher

问题描述 #

我希望用DOI作为期刊的通用标识符，现有某期刊的DOI列表：
['10.1001/jamacardio.2016.5501','10.1001/jamacardio.2017.3145','10.1001/jamacardio.2018.3029','10.1001/jamacardio.2020.5573','10.1001/jamacardio.2020.0647']（实际列表更长）。需要找出该列表中的最长公共子串，之前尝试过SequenceMatcher但它只能比较两个字符串的相似度，写的代码如下：

journal_list = ['10.1001/jamacardio.2016.5501','10.1001/jamacardio.2017.3145','10.1001/jamacardio.2018.3029','10.1001/jamacardio.2020.5573','10.1001/jamacardio.2020.0647']

def longestSubstring(str1,str2):
    #initialize SequenceMatcher object with input string
    seqMatch = SequenceMatcher(None,str1,str2)
    #find match of longest sub-string
    #output will be like Match(a=0, b=0, size=5)
    match = seqMatch.find_longest_match(0, len(str1), 0, len(str2))
    if (match.size!=0):
        print (str1[match.a: match.a + match.size]) 
    else:
        print ('No longest common sub-string found')

for journal in journal_list:
    str1 = journal_list[1]

print(longestSubstring(str1,journal))

预期输出为：'10.1001/jamacardio.20'

解决方案 #

要处理多个字符串的最长公共子串，不能仅做两两比较，正确思路是：以第一个字符串为基准，生成它的所有可能子串（从最长到最短），逐一检查是否为所有其他字符串的子串，第一个满足条件的就是最长公共子串。

代码实现 #

def longest_common_substring(str_list):
    if not str_list:
        return ""
    
    # 以第一个字符串为基准，从最长子串开始遍历
    base_str = str_list[0]
    max_length = len(base_str)
    
    for length in range(max_length, 0, -1):
        for start_idx in range(max_length - length + 1):
            current_sub = base_str[start_idx:start_idx+length]
            # 检查所有其他字符串是否包含该子串
            if all(current_sub in s for s in str_list[1:]):
                return current_sub
    return ""

# 测试代码
journal_list = ['10.1001/jamacardio.2016.5501','10.1001/jamacardio.2017.3145','10.1001/jamacardio.2018.3029','10.1001/jamacardio.2020.5573','10.1001/jamacardio.2020.0647']
print(longest_common_substring(journal_list))  # 输出: 10.1001/jamacardio.20

原代码问题分析 #

1. journal_list未初始化赋值，直接运行会报错；
2. 循环内str1 = journal_list[1]的逻辑无意义，每次循环都将str1重置为第二个元素；
3. 仅实现了两个字符串的最长子串比较，未覆盖整个列表的公共子串判断。

内容的提问来源于stack exchange，提问作者msci