LongestDuplicateSubstring.java

package array;

import java.util.HashSet;

/**
 * @author :DengSiYuan
 * @date :2019/11/18 20:54
 * @desc : 1044.最长重复子串
 * 【题目】
 *      给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
 *      返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）
 * 【示例】
 *      示例 1：
 *          输入："banana"
 *          输出："ana"
 *      示例 2：
 *          输入："abcd"
 *          输出：""
 * 【提示】
 *      2 <= S.length <= 10^5
 *      S 由小写英文字母组成。
 */
public class LongestDuplicateSubstring {

    /**
     *Rabin-Karp具有多项式滚动哈希。
     *搜索给定长度的子字符串发生至少2次。
     *如果子字符串退出，则返回起始位置，否则返回-1。
     */
    public int search(int L, int a, long modulus, int n, int[] nums) {
        // compute the hash of string S[:L]
        long h = 0;
        for (int i = 0; i < L; ++i){
            h = (h * a + nums[i]) % modulus;
        }
        // already seen hashes of strings of length L
        HashSet<Long> seen = new HashSet<>();
        seen.add(h);
        // const value to be used often : a**L % modulus
        long aL = 1;
        for (int i = 1; i <= L; ++i){
            aL = (aL * a) % modulus;
        }
        for (int start = 1; start < n - L + 1; ++start) {
            // compute rolling hash in O(1) time
            h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;
            h = (h + nums[start + L - 1]) % modulus;
            if (seen.contains(h)){
                return start;
            }
            seen.add(h);
        }
        return -1;
    }

    public String longestDupSubstring(String S) {
        int n = S.length();
        // convert string to array of integers
        // to implement constant time slice
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i){
            nums[i] = (int)S.charAt(i) - (int)'a';
        }
        // base value for the rolling hash function
        int a = 26;
        // modulus value for the rolling hash function to avoid overflow
        long modulus = (long)Math.pow(2, 32);

        // binary search, L = repeating string length
        int left = 1, right = n;
        int L;
        while (left != right) {
            L = left + (right - left) / 2;
            if (search(L, a, modulus, n, nums) != -1){
                left = L + 1;
            }
            else{
                right = L;
            }
        }

        int start = search(left - 1, a, modulus, n, nums);
        return start != -1 ? S.substring(start, start + left - 1) : "";
    }

}