js实现找出字符串中重复最长的字串

在JavaScript中，找出字符串中重复最长的子串可以通过多种算法实现，其中一个高效的方法是使用动态规划。下面提供一个基于动态规划的示例实现：

function longestDupSubstring(S) {
    const MOD = 1000000007;
    const base = 26; // 字母的总数
    let n = S.length;
    let maxLen = 0; // 最长相等子串的长度
    let startIndex = 0; // 最长相等子串的起始索引
    let hash = 0; // 当前子串的哈希值
    let basePower = 1; // base的幂，用于计算新的哈希值

    // 计算最大的base的n-1次幂
    for (let i = 0; i < n; i++) {
        basePower = (basePower * base) % MOD;
    }

    // 计算字符串的哈希值
    for (let i = 0; i < n; i++) {
        hash = (hash * base + S.charCodeAt(i) - 'a'.charCodeAt(0)) % MOD;
    }

    // 存储每个字符出现的哈希值和对应的索引
    const indexMap = new Map([[hash, 0]]);

    // 使用滚动哈希来计算子串的哈希值
    for (let i = 1; i < n; i++) {
        hash = (hash * base + S.charCodeAt(i) - 'a'.charCodeAt(0)) % MOD;
        if (indexMap.has(hash)) {
            let j = indexMap.get(hash);
            if (S.slice(j, i) === S.slice(j + maxLen, i + maxLen)) {
                startIndex = j;
                maxLen = i - j;
            }
        } else {
            indexMap.set(hash, i);
        }
    }

    // 返回最长重复子串
    return S.slice(startIndex, startIndex + maxLen);
}

// 测试用例
console.log(longestDupSubstring("banana")); // 应该返回 "an"

这段代码首先计算了字符串的哈希值，然后使用一个哈希表来存储出现过的子串哈希值及其起始索引。通过滚动窗口的方法，我们可以在O(n)的时间复杂度内找到最长的重复子串。