Longest Duplicate Substring| CPP

cplusplus-leetcode-1044.cpp

class Solution {
    static const int MODULAR = INT_MAX;
    static const int BASE = 26;
    vector<int> normalized;
    vector<int> power;
public:
    // O(n)
    string find(string &s, int len) {
        int hash = 0;
        unordered_map<int, unordered_set<int>> mp;
        for(int i = 0; i < len; ++i)
            hash = ((long)hash*BASE)%MODULAR + normalized[i];

        mp[hash].insert(0);

        int del_base = power[len-1];
        for(int i=1; i+len <= s.size(); ++i) {
            // ban -> ana
            hash = ((hash - (long)del_base * normalized[i-1])%MODULAR + MODULAR)% MODULAR;  // watch out
            hash = (((long)hash*BASE)% MODULAR + normalized[i+len-1]) % MODULAR;

            if(mp.find(hash) != end(mp)) {
                // check if collision or not
                for(const int& idx : mp[hash])
                    if(s.substr(idx, len) == s.substr(i,len))
                        return s.substr(i,len);
            }
            mp[hash].insert(i);
        }
        return "";
    }
    // O(nlogn)
    string longestDupSubstring(string S) {
        int n = S.size(),
                lo = 1,
                hi = n;
        string rst = "";

        power.resize(n, 1);
        normalized.resize(n,0);

        for(int i=1; i < n; ++i)
            power[i] = ((long)power[i-1] * BASE) % MODULAR;

        for(int i=0; i < n; ++i)
            normalized[i] = S[i] - 'a';

        while( lo < hi) {
            int mid = lo + ((hi-lo)>>1);
            string ans = find(S,mid);
            if( !ans.empty() ) {
                lo = mid+1;
                if(ans.size() > rst.size()) rst = ans;
            } else hi = mid;
        }
        return rst;
    }
    
};