1044.Longest-Duplicate-Substring

1044. Longest Duplicate Substring

题目地址

https://leetcode.com/problems/longest-duplicate-substring/

题目描述

Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times.  (The occurrences may overlap.)

Return any duplicated substring that has the longest possible length.  (If S does not have a duplicated substring, the answer is "".)

Example 1:
Input: "banana"
Output: "ana"

Example 2:
Input: "abcd"
Output: ""

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

代码

Approach 1: Binary Search + Rabin-Karp

Complexity Analysis

• Time complexity : O(N_log_N). O(logN) for the binary search and O(N) for Rabin-Karp algorithm.

• Space complexity : O(N) to keep the hashset.

class Solution {
  public String longestDupSubstring(String S) {
    int n = S.length();
    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);

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

    int start = search(left - 1, a, modulus, n, nums);
    return S.substring(start, start + left - 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;
    }

    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;
      } else {
        seen.add(h);
      }
    }

    return -1;
  }
}