### 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));
}

};