多字符串最长公共子串（Longest Common Substring）代码测试异常求助

问题根源 #

你的代码采用迭代两两求最长公共子串的逻辑：先计算前两个字符串的最长公共子串，再用这个结果和第三个字符串计算，以此类推。这种逻辑在处理多字符串时存在缺陷——前两个字符串的最长公共子串可能并非所有输入字符串共有的子串，导致后续无法找到正确的共同子串。

测试用例执行过程分析 #

针对测试用例ZZZABXXX、XXXYYYAB、ABYYYZZZ：

1. 第一步计算ZZZABXXX和XXXYYYAB的最长公共子串：两者的最长连续公共子串是XXX（长度3），比AB（长度2）更长，因此result被赋值为XXX。
2. 第二步用XXX和ABYYYZZZ计算最长公共子串：这两个字符串没有连续的公共子串，因此返回空字符串，最终输出为空。

但实际上三个字符串共有的最长公共子串是AB，只是它不是前两个字符串的最长公共子串，导致当前逻辑无法捕捉到。

修复方案 #

换一种思路：以最短的输入字符串为基准，枚举它的所有可能子串（按长度从长到短排序），第一个在所有其他字符串中都存在的子串，就是所有输入的最长公共子串。这种方法能确保找到的是所有字符串共有的最长连续子串。

修改后的完整代码：

// 检查子串是否存在于目标字符串中
const hasSubstring = (str, sub) => str.includes(sub);

// 找出多个字符串的最长公共子串
const longestCommonSubstring = (strings) => {
    if (strings.length === 0) return '';
    // 以最短字符串为基准，减少枚举次数
    const shortestStr = strings.reduce((a, b) => a.length <= b.length ? a : b);
    
    // 按子串长度从长到短枚举
    for (let len = shortestStr.length; len > 0; len--) {
        // 枚举所有长度为len的子串
        for (let start = 0; start <= shortestStr.length - len; start++) {
            const sub = shortestStr.substring(start, start + len);
            // 检查是否所有字符串都包含该子串
            const allInclude = strings.every(str => hasSubstring(str, sub));
            if (allInclude) {
                return sub;
            }
        }
    }
    return ''; // 无公共子串
};

// 处理终端输入
const args = process.argv.slice(2);
if (args.length === 0) {
    console.log('');
} else {
    const result = longestCommonSubstring(args);
    console.log(result);
}

代码说明 #

1. 以最短字符串为基准：减少需要枚举的子串数量，提升效率。
2. 从最长子串开始枚举：一旦找到符合条件的子串，直接返回，无需继续检查更短的子串。
3. 全局检查：确保找到的子串是所有输入字符串共有的，避免了两两迭代的局限性。

运行修改后的代码，测试用例ZZZABXXX XXXYYYAB ABYYYZZZ会正确输出AB。

内容的提问来源于stack exchange，提问作者1641_Shourav Chy