1062. Longest Repeating Substring (bs + rolling hash

T: O(nlogn)

S: O(n), set size

class Solution {
    public int longestRepeatingSubstring(String s) {
        int len = s.length();
        int left = 0;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left)/2;
            if (found(s, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (found(s, right)) { // right is longer, test first
            return right;
        }
        if (found(s, left)) {
            return left;
        }
        return 0;
    }
    private boolean found(String s, int len) {
        long hash = 0L;
        long base = 26L;
        long mod = 100_000_007L;

        Set<Long> set = new HashSet<>();
        long powBaseLen = 1L;
        for (int i = 0; i < len; i++) {
            powBaseLen = (powBaseLen*base) % mod;
        }
        
        for (int i = 0; i < s.length(); i++) {
            
            hash = (hash * base + (s.charAt(i) - 'a')) % mod;
            if (i >= len) {
                hash = (hash - (s.charAt(i-len) - 'a')*powBaseLen%mod + mod)%mod;
            }
            if (i >= len-1) { // sliding window has new value, 才要檢查 or 塞入 hash
                if (set.contains(hash)) {
                    return true;
                }
                set.add(hash);
            }
        }
        return false;
        
    }
}

/*
slding window

xxx[abcd]exxx => cal hash

xxxa[bcde]xxx => cal new hash

1. 
so add new hash with e
hash = (hash * base + (s.charAt(i) - 'a')) % mod;

2.
remove a
hash = (hash - (s.charAt(i-len) - 'a')*powBaseLen%mod + mod)%mod;

3.
when reach sliding window end, add hash, or check is it existed
if (i >= len-1) { // sliding window has new value, 才要檢查 or 塞入 hash
    if (set.contains(hash)) {
        return true;
    }
    set.add(hash);
}

*/