JavaScript查找字符串中长度≥2的非重叠重复子串方法

原有代码问题分析 #

当前编写的代码存在以下局限，无法满足需求：

• 通过正则/.{1,2}/gm将字符串固定按2字符为单位切分，只能匹配固定切分位置上长度恰好为2的重复块
• 无法支持长度大于2的子串匹配，也会漏掉跨切分位置的重复模式

实现思路 #

要覆盖所有长度≥2的非重叠重复子串，按以下逻辑实现即可：

• 遍历所有合法的模式长度：最小长度为2，最大长度不超过字符串总长度的1/2（非重叠重复至少出现2次，子串长度不可能超过总长度的一半）
• 对每个长度的子串，逐位置滑动截取，记录每个子串首次出现的起始索引
• 当后续遇到相同子串时，校验是否和之前的出现位置非重叠：当前子串的起始位置 ≥ 前一次出现的起始位置 + 子串长度，满足条件则判定为有效重复模式
• 最终对结果去重，可按子串长度从长到短排序，优先选取更长的模式获得更高的压缩率

可运行代码实现 #

function findNonOverlapRepeats(str) {
    const validPatterns = new Set();
    const totalLen = str.length;
    // 遍历所有可能的模式长度
    for (let patternLen = 2; patternLen <= Math.floor(totalLen / 2); patternLen++) {
        const firstOccur = new Map(); // 存储子串第一次出现的起始位置
        for (let i = 0; i <= totalLen - patternLen; i++) {
            const current = str.slice(i, i + patternLen);
            if (firstOccur.has(current)) {
                const prevStart = firstOccur.get(current);
                // 校验非重叠
                if (i >= prevStart + patternLen) {
                    validPatterns.add(current);
                }
            } else {
                firstOccur.set(current, i);
            }
        }
    }
    // 按长度降序返回，优先返回压缩效率更高的长模式
    return Array.from(validPatterns).sort((a, b) => b.length - a.length);
}

// 测试示例
console.log(findNonOverlapRepeats("abcdabcr"));
// 输出结果: ['abc', 'ab', 'bc']

测试说明 #

传入测试字符串"abcdabcr"时，函数会正确识别出最长重复模式abc，同时返回所有符合长度要求的非重叠重复子串。如果用于压缩场景，直接选取最长的匹配模式即可获得最优压缩效果。

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