LeetCode June Challenge - Day 19

Problem: LeetCode June Challenge - Day 19

Ideas:

  1. Had to use the hints for this one, but they are all the ideas you need. The hash functions I used for Rabin Karp is $$ (\sum_i p^i \cdot S[i])\ mod\ 10^9+1 $$ so I can calculate the hash of a substring using the previous hash in O(1).

Solution:

class Solution {
    int rabin_karp(string &S, int m){
        const int p = 3, pinv = 333333334, mod = 1e9+1;
        unordered_map<long long, vector<int>> umap;
        long long hash = S[0];
        long long power = 1;

        for(int i=1; i<m; ++i){
            power = (power * p) % mod;
            hash = (hash + S[i] * power) % mod;
        }
        umap[hash].push_back(0);

        for(int i=m; i<S.size(); ++i){
            hash = (((hash-S[i-m])%mod)*pinv + power*S[i] % mod)%mod;
            if(hash < 0) hash += mod;

            for(int index : umap[hash])
                if(S.compare(i-m+1, m, S, index, m) == 0)
                    return i-m+1;

            umap[hash].push_back(i-m+1);
        }
        return -1;
    }

public:
    string longestDupSubstring(string S) {
        int ans = -1;
        int lo = 1, hi = S.length()-1;

        while(lo <= hi){
            int m = (lo+hi)/2;
            int aux = rabin_karp(S,m);
            if(aux != -1) lo = m+1, ans = aux;
            else hi = m-1;
        }

        return (ans == -1 ? "" : S.substr(ans, hi));
    }

};