字符串哈希模板

bool isprime(int n) {if (n <= 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}
int findPrime(int n) {while (!isprime(n)) {n++;}return n;
}void slove(){mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int P = findPrime(rng() % 900000000 + 100000005);string s;cin>>s;int n=s.size();s='.'+s;vector<int> h(n + 3,0), p(n + 3,0);p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*10LL%P;//预处理过程h[i]=(h[i-1]*10LL+s[i]-'a')%P;//计算字符串的哈希值}auto get = [&](int l, int r) {return (h[r]+1LL*(P-h[l-1])*p[r-l+1])%P;    };
}