发布时间：2024-07-31

字符串哈希

#define int long long  
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int mod=1e9+9,B=rng()%mod;//B=117
int h[N],pw[N];
int getHash(int l,int r){
    return h[r]-h[l-1]*pw[r-l+1]; 
}
void init(){
    for(int i=0;i<s.size();i++){
        h[i+1]=(h[i]*B%mod+s[i])%mod;
        pw[i+1]=pw[i]*B%mod;
    }
}