shared by my friend - Ph.D. Ex-Microsoft, Amazon engineer, Find longest repeated substring with overlapping - Leetcode https://github.com/jianminchen/100-hard-level-algorithms-2018-summer-campaign/tree/master/LongestRepeatedSubstring-overlap

FindLongestRepeatedSubstring.java

class Solution {
    int a = 26, mod = 1<<30;
    public String longestDupSubstring(String S) {
        int lo = 1, hi = S.length()-1;
        while(lo<=hi){
            int mid = lo+(hi-lo)/2, startIndex = search(S,mid);
            if(startIndex==-1){
                hi = mid-1;
            }
            else{
                lo = mid+1;
            }
        }
        
        int startIndex = search(S,hi);
        return startIndex==-1 ? "" : S.substring(startIndex,startIndex+hi);
    }
    
    public int search(String S, int len){
        long h = 0, aL = 1;
        for(int i=0; i<len; i++){
            h = (h*a%mod + S.charAt(i) - 'a')%mod;
            aL = aL*a%mod;
        }
        
        HashMap<Long,List<Integer>> visited = new HashMap();
        visited.put(h,new ArrayList<Integer>());
        visited.get(h).add(0);
        for(int i=1; i<S.length()-len+1; i++){
            h = ((h*a%mod-(S.charAt(i-1) - 'a')*aL%mod+mod)%mod+(S.charAt(i+len-1) - 'a'))%mod;
            if(visited.containsKey(h)){
                for(int start : visited.get(h)){
                    if(S.substring(start,start+len).equals(S.substring(i,i+len))) return i;
                }            
            }
            else{
                visited.put(h,new ArrayList<Integer>());           
            }
            visited.get(h).add(i);     
        }
        return -1;
    }
}