Untitled

unknown
plain_text
24 days ago
1.5 kB
1
Indexable
Never
```class Solution {
public:
const int PRIME = 31;
const int MOD = 1e9 + 9;
unordered_set<long long> isSeen;

long long binExp(long long x, long long n){
long long res = 1;
while(n){
if(n&1) res = (res * x) % MOD;
x = (x * x)%MOD;
n>>=1;
}
return res;
}

bool isPossible(vector<long long> &h,  vector<long long> &power, int len){
cout<<len<<"\n";
long long pw = 1;
for(int i=int(h.size())-1; i-len>=0; i--){
long long currHash = ((h[i] - h[i-len] + MOD)%MOD * pw)%MOD;
cout<<i<<" "<<currHash<<"\n"; //hash of i is stored at h[i+1]
if(isSeen.count(currHash)) return true;
isSeen.insert(currHash);
pw = (pw * power[1])%MOD;
}
return false;
}

int longestRepeatingSubstring(string word) {
int n = word.size();
vector<long long> power(n+1);
power[0] = 1;
for (int i = 1; i < (int)power.size(); i++)
power[i] = (power[i-1] * PRIME) % MOD;
vector<long long> h(n + 1, 0);
for (int i = 0; i < n; i++)
h[i+1] = (h[i] + (word[i] - 'a' + 1) * power[i]) % MOD;
int low = 1, high = n, ans = 0;
while(low<=high){
int mid = low + (high-low)/2;
if(isPossible(h, power, mid)){
ans = mid;
low = mid+1;
}
else{
high = mid-1;
}
}
return ans;
}
};```