最长公共子串（LCS）算法Bug排查：起始匹配字符丢失问题

你的lcsm函数在寻找多字符串最长公共子串时，当目标序列前存在相同起始字符的前缀片段，会丢失结果的第一个字符。比如第二个测试用例中，正确结果应为'123456789034357890'，但函数输出少了开头的'1'。

问题根源分析 #

原代码的核心逻辑缺陷在内层循环的匹配处理：

• 当seq1[ind1+i]与seq2[ind2]不匹配时，直接清空motif并重置i=0，然后继续下一个ind2。这种处理会中断当前的匹配进程，并且没有考虑**从当前ind2位置重新尝试匹配seq1[ind1]**的可能。
• 以第二个测试用例为例：seq1是最短字符串'123456789034357890'，seq2是'123123456789034357890890357890'。当ind1=0时，内层循环先匹配到seq2前3个字符'123'，但第4个字符seq1[3]='4'和seq2[3]='1'不匹配，此时代码清空motif，从ind2=4继续循环。但seq2[4]='2'和seq1[0]='1'不匹配，导致完全错过了seq2中从索引3开始的'1234567890...'的匹配，只能后续从ind1=1开始匹配，最终结果丢失了第一个'1'。

修复方案 #

换一种更可靠的匹配逻辑：从最短字符串的所有可能子串出发，固定起始位置后逐步延长子串长度，一旦找到不满足“存在于所有字符串”的子串，就停止延长（因为更长的子串必然也不满足），同时记录最长的有效子串。

修复后的代码：

def lcsm(string_list):
    if not string_list:
        return ''
    
    # 按长度升序排序，优先从最短字符串枚举子串
    strands = sorted(string_list, key=len)
    shortest_str = strands[0]
    longest_motif = ''
    
    # 遍历最短字符串的所有起始位置
    for start in range(len(shortest_str)):
        # 子串长度至少要比当前最长结果长才需要检查
        min_length = len(longest_motif) + 1
        # 遍历所有可能的结束位置，从能形成更长子串的位置开始
        for end in range(start + min_length, len(shortest_str) + 1):
            current_motif = shortest_str[start:end]
            # 检查当前子串是否存在于所有字符串中
            if all(current_motif in s for s in strands):
                longest_motif = current_motif
            else:
                # 子串是逐步延长的，一旦不匹配，更长的子串肯定也不匹配，直接跳出
                break
    return longest_motif

验证结果 #

运行原测试用例：

print('right: ', lcsm(['123456789034357890', 
            '123456789034357890890357890', 
            '4612345678901234567890343578904654734357890', 
            '12356734121234567890343578903456789035789012345']))        

print('fixed: ', lcsm(['123456789034357890', 
            '123123456789034357890890357890', 
            '4612345678901234567890343578904654734357890', 
            '12356734121234567890343578903456789035789012345']))

输出结果：

right:  123456789034357890
fixed:  123456789034357890

两个测试用例都能返回正确的最长公共子串。

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