Description

Submission

class Solution {
    bool checkRepeat(string& s, int len) {
        long sum = 0;
        const long M = 1e9 + 7;
        const long base = 26;
        long hash = 0;
        long t = 1;

        set<long> hashSet;

        for(int i = 0; i < len; ++i) {
            t = t * base % M;
        }

        for(int i = 0; i < s.length(); ++i) {
            hash = (hash * base + (s[i] - 'a')) % M;

            if(i >= len) {
                hash = (hash + M - (s[i-len] - 'a') * t) % M;
            }

            if(i >= len - 1) {
                if(hashSet.count(hash)) return true;
                hashSet.insert(hash);
            }
        }

        return false;
    }
public:
    int longestRepeatingSubstring(string s) {
        int lower = 0, upper = s.length() - 1;

        while(lower < upper) {
            int mid = upper - (upper - lower) / 2;

            if(checkRepeat(s, mid)) {
                lower = mid;
            } else {
                upper = mid - 1;
            }
        }

        if(checkRepeat(s, lower)) {
            return lower;
        }
        return 0;
    }
};