技术问询：如何获取首个出现的最长非重叠重复子字符串？

我之前正好有获取首个出现的最长非重叠重复子字符串的需求，一开始找到的是C++的实现方案，后来把它转换成了JavaScript版本，分享给有同样需求的开发者参考～

需求说明 #

我们要找的是字符串中长度最长、重复出现且两次出现的子串没有重叠的子字符串，并且返回第一个符合条件的最长子串。举几个直观的例子：

• 输入 "abcabcabc"，输出 "abc"（两次出现的位置0-2和3-5，无重叠）
• 输入 "aaaaa"，输出 "aa"（两次出现的位置0-1和2-3，无重叠）
• 输入 "abcdabcdxyz"，输出 "abcd"

JavaScript实现代码 #

function findLongestNonOverlappingRepeatingSubstring(str) {
    const strLength = str.length;
    let longestSub = "";

    // 从最长的可能子串长度开始遍历（至少要能重复两次，所以最大长度是原字符串的一半）
    for (let subLen = Math.floor(strLength / 2); subLen > 0; subLen--) {
        const subPosMap = new Map();
        for (let start = 0; start <= strLength - subLen; start++) {
            const currentSub = str.slice(start, start + subLen);
            if (subPosMap.has(currentSub)) {
                // 检查两次出现的子串是否不重叠：当前起始位置 >= 第一次出现的起始位置 + 子串长度
                const firstPos = subPosMap.get(currentSub);
                if (start >= firstPos + subLen) {
                    // 因为是从最长长度开始找的，第一个符合条件的就是我们要的结果
                    return currentSub;
                }
            } else {
                subPosMap.set(currentSub, start);
            }
        }
    }
    // 没有找到符合条件的子串时返回空字符串
    return longestSub;
}

// 测试用例
console.log(findLongestNonOverlappingRepeatingSubstring("abcabcabc")); // "abc"
console.log(findLongestNonOverlappingRepeatingSubstring("abababx")); // "ab"
console.log(findLongestNonOverlappingRepeatingSubstring("aaaaa")); // "aa"
console.log(findLongestNonOverlappingRepeatingSubstring("abcdxyz")); // ""

代码逻辑解释 #

1. 从长到短遍历子串长度：我们从原字符串长度的一半开始往下遍历，这样一旦找到符合条件的子串，就是最长的那个，无需再检查更短的子串，能提升查找效率。
2. 记录子串首次出现位置：用Map存储每个子串第一次出现的起始索引，当再次遇到相同子串时，判断两次出现的位置是否满足“不重叠”的条件（当前起始位置 >= 首次位置 + 子串长度）。
3. 直接返回结果：因为是从最长长度开始查找，第一个满足条件的子串就是首个出现的最长非重叠重复子串，直接返回即可。

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