多个字符串中最长且最常见的公共子串

Question

这不应该是一个新问题，但我找不到解决方案（对于多个字符串，而不仅仅是两个字符串）。

基本上，我有一个字符串列表，它们可能共享也可能不共享一些公共子字符串。任务是找到尽可能多的字符串共享的最长子串。

例如，字符串列表为：['abc_001', 'abc_002', 'x_abc', 'y_abc', 'z_abc_1', 'z_abc_2', '123_a', '123_b', '123_c']。该列表的 LCS 应该是“abc”（注意“123”在 3 个字符串中，但“abc”在 6 个字符串中）。

有什么想法可以解决这个问题吗？我猜蛮力可以工作吗？但我想知道是否有更好的方法。

非常感谢您的宝贵时间。

Answer 1

经过一番推理，我想出了这个可能的解决方案：

def longest_common_substring(lst):
    
    suffixes = [s[i:] for s in lst for i in range(len(s))]
    suffixes.sort()
    
    longest_common = ''
    
    for i in range(1, len(suffixes)):
        common = ''
        j = 0
        while j < min(len(suffixes[i]), len(suffixes[i-1])) and suffixes[i][j] == suffixes[i-1][j]:
            common += suffixes[i][j]
            j += 1
         corrente, aggiorna la stringa comune più lunga
        if len(common) > len(longest_common):
            longest_common = common
    
    return longest_common

lst = ['abc_001', 'abc_002', 'x_abc', 'y_abc', 'z_abc_1', 'z_abc_2', '123_a', '123_b', '123_c']
print(longest_common_substring(lst))

输出：

abc_00