1044. Longest Duplicate Substring

[Tcdian]

1044. Longest Duplicate Substring

给出一个字符串 S，考虑其所有 重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

Example 1

Input: "banana"
Output: "ana"

Example 2

Input: "abcd"
Output: ""

Note

• 2 <= S.length <= 10^5
• S consists of lowercase English letters.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} S
 * @return {string}
 */
var longestDupSubstring = function(S) {
    let left = 1;
    let right = S.length - 1;
    let result = '';
    while(left <= right) {
        const mid = (left + right) >> 1;
        const dupSubString = rkSearch(S, mid);
        if (dupSubString !== '') {
            result = dupSubString;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
};

function rkSearch(S, len) {
    const cache = new Set();
    const mod = 2 ** 32;
    let h = 0;
    for (let i = 0; i < len; i++) {
        h = ((h * 26) % mod + S.codePointAt(i) - 97) % mod;
    }
    cache.add(h);
    let al = 1;
    for (let i = 1; i < len; i++) {
        al = (al * 26) % mod;
    }
    for (let i = 1; i + len <= S.length; i++) {
        h = (((h - ((S.codePointAt(i - 1) - 97) * al + mod) % mod) * 26) % mod
            + S.codePointAt(i + len - 1) - 97) % mod;
        if (cache.has(h)) {
            return S.slice(i, i + len);
        }
        cache.add(h);
    }
    return '';
}

• TypeScript Solution

function longestDupSubstring(S: string): string {
    let left = 1;
    let right = S.length - 1;
    let result = '';
    while(left <= right) {
        const mid = (left + right) >> 1;
        const dupSubString = rkSearch(S, mid);
        if (dupSubString !== '') {
            result = dupSubString;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
};

function rkSearch(S: string, len: number): string {
    const cache: Set<number> = new Set();
    const mod = 2 ** 32;
    let h = 0;
    for (let i = 0; i < len; i++) {
        h = ((h * 26) % mod + (S.codePointAt(i) as number) - 97) % mod;
    }
    cache.add(h);
    let al = 1;
    for (let i = 1; i < len; i++) {
        al = (al * 26) % mod;
    }
    for (let i = 1; i + len <= S.length; i++) {
        h = (((h - ((S.codePointAt(i - 1) as number - 97) * al + mod) % mod) * 26) % mod
            + (S.codePointAt(i + len - 1) as number) - 97) % mod;
        if (cache.has(h)) {
            return S.slice(i, i + len);
        }
        cache.add(h);
    }
    return '';
}