June Leetcoding Challenge(6.19)

LeetCode六月挑战（6.19 ）Longest Duplicate Substring LeetCode 1044

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:

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

思路

• 二分答案，得到长度以后，判断字符串是否相同，采用Robin-Karp算法，计算不同长度的字符串对应的哈希值。

  e.g.
  s = banana;
  //将每个字符转换为int类型数组
  c(b) = s.charAt(0) -'a';
  c(a) = s.charAt(1) - 'a';
  c(n) = s.charAt(2) - 'a';
  hash(bana) = c(b)*26^3+c(a)*26^2+c(n)*26^1+c(a)*26^0;
  hash(anan) = (hash(bana) - c(b)*26^3)*26 + c(n)*26^0;

代码

java

class Solution {
    public String longestDupSubstring(String S) {
        int l = 0;
        int r = S.length() - 1;
        
        while (l < r) {
            int m = l + ((r - l + 1) >> 1);
            
            if (isDuplicatePresent(S, m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        
        return findDuplicate(S, l);
    }
    
    private boolean isDuplicatePresent(String S, int length) {
        if (length == 0)
            return true;
        
        return findDuplicate(S, length) != null;
    }
    
    private String findDuplicate(String S, int length) {        
        long hash = 0;
        long prime = 26;
        long firstEntryPower = 1;
        for (int i = 0; i < length; i++) {
            firstEntryPower *= prime;
            hash = hash * prime + (S.charAt(i) - 'a');
        }
        
        Map<Long, Integer> map = new HashMap<>();
        map.put(hash, 0);
        
        for (int i = length; i < S.length(); i++) {
            hash = hash * prime + (S.charAt(i) - 'a');
            hash -= firstEntryPower * (S.charAt(i - length) - 'a');
            
            if (map.containsKey(hash)) {
                int index = map.get(hash);
                return S.substring(index, index + length);
            }
            
            map.put(hash, i - length + 1);
        }
        
        return null;
    }
}