本文主要是介绍基于mt19937_64的字符串哈希（板子整理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
引自tourist的哈希板子，引入和时间相关的随机值mt19937_64，所以不会被卡掉
入参：传入string
使用：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());struct hash61 {static const uint64_t md = (1LL << 61) - 1;static uint64_t step;static vector<uint64_t> pw;uint64_t addmod(uint64_t a, uint64_t b) const {a += b;if (a >= md) a -= md;return a;}uint64_t submod(uint64_t a, uint64_t b) const {a += md - b;if (a >= md) a -= md;return a;}uint64_t mulmod(uint64_t a, uint64_t b) const {uint64_t l1 = (uint32_t) a, h1 = a >> 32, l2 = (uint32_t) b, h2 = b >> 32;uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;uint64_t ret = (l & md) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;ret = (ret & md) + (ret >> 61);ret = (ret & md) + (ret >> 61);return ret - 1;}void ensure_pw(int sz) {int cur = (int) pw.size();if (cur < sz) {pw.resize(sz);for (int i = cur; i < sz; i++) {pw[i] = mulmod(pw[i - 1], step);}}}vector<uint64_t> pref;int n;template<typename T>hash61(const T& s) {n = (int) s.size();ensure_pw(n + 1);pref.resize(n + 1);pref[0] = 1;for (int i = 0; i < n; i++) {pref[i + 1] = addmod(mulmod(pref[i], step), s[i]);}}inline uint64_t operator()(const int from, const int to) const {assert(0 <= from && from <= to && to <= n - 1);return submod(pref[to + 1], mulmod(pref[from], pw[to - from + 1]));}
};uint64_t hash61::step = (md >> 2) + rng() % (md >> 1);
vector<uint64_t> hash61::pw = vector<uint64_t>(1, 1);string s;
int n;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>s;auto hs=hash61(s);int l=0,r=n-1;cout<<hs(l,r)<<endl;return 0;
}
这篇关于基于mt19937_64的字符串哈希（板子整理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
