PROG-T1154: Longest Repeated Substring

#include <iostream>
#include <map>
using namespace std;

#define lli long long
const lli PB = 1e9 + 7;

int len, tr;
bool Repeated(char str[], int x){
    map<lli, int> mp;
    lli base = 1;
    lli hsh = 0;
    // Hash first substring
    for(int i = 0; i < x; ++i){
        hsh *= PB;
        hsh += str[i];
        if(i != 0){
            base *= PB;
        }
    }
    mp.insert(make_pair(hsh, 1));
    // Rolling hash
    for(int i = x; i < len; ++i){
        hsh -= str[i - x] * base;
        hsh *= PB;
        hsh += str[i];
        if(mp.find(hsh) == mp.end()){
            mp.insert(make_pair(hsh, 1));
        } else {
            ++mp[hsh];
            if(mp[hsh] >= tr){
                return true;
            }
        }
    }
    return false;
}

int main(){

    scanf("%d", &len);
    scanf("%d", &tr);

    char str[len + 2];
    scanf(" %s", str);

    int l = 1;
    int r = len;
    int mx = 1;
    while(l <= r){
        int m = (l + r) / 2;
        if(Repeated(str, m)){
            mx = max(mx, m);
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    cout << mx;

    return 0;
}