Untitled

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