基于mt19937_64的字符串哈希(板子整理)
2023-12-25 00:11:51
引自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;
}
文章来源:https://blog.csdn.net/Code92007/article/details/135188295
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!