Description

Submission

class Solution {
    string ret;

    bool found(string& s, int len) {
        unordered_set<uint64_t> hashSet;
        uint64_t hash = 0;
        const uint64_t base = 31;
        uint64_t coeff = 1;

        for(int i = 0; i < len; ++i) {
            coeff *= base;
        }

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

            if(i >= len) {
                hash = hash - coeff * (s[i-len]-'a');
            }

            if(i >= len - 1) {
                if(hashSet.count(hash)) {
                    ret = s.substr(i - len + 1, len);
                    return true;
                }
                hashSet.insert(hash);
            }
        }
        return false;
    } 

public:
    string longestDupSubstring(string s) {
        ret = "";
        int lower = 0, upper = s.length() - 1;

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

            if(found(s, mid)) {
                lower = mid;
            } else {
                upper = mid - 1;
            }
        }
        if(!found(s, lower)) {
            return "";
        }
        return ret;
    }
};