хэши

ll MD  = 1000000009;
ll L  = 53;
ll MAXSIZE = 200005;
vector<ll>st(MAXSIZE,0);
vector<ll> createHash(string s){
    vector<ll>h(s.size()+1,0);
    for(int i=0;i<s.size();++i){
        h[i+1] = (h[i]*L +s[i])%MD;
    }
    return h;
}
ll getHash(vector<ll>&h ,ll l,ll r){
    return (h[r] - h[l-1]*st[r-l+1] +MD*MD)%MD;
}

st[0] = 1;
    for(int i=1;i<MAXSIZE;++i){
        st[i] = (st[i-1]*L)%MD;
    }