首页 > 代码库 > hash 模板 x
hash 模板 x
不懂hash是什么的盆友给出直通车:滴滴滴,开车啦~
如果你看懂了的话:
hash模板来也~
#include <cstdio>#include <string>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N = 1e5 + 6; //10006const int D = 131; //质数 const int MD = 1e9 + 7; //大质数 int n;string s;unsigned long long f[N], g[N]; //g[i]为D的i次方 void prehash(int n) //进行预处理 {// 预处理时,注意到数字可能很大,对一个数 MD 取模 f[0] = s[0];//预处理前缀和(进行强制类型转) for(int i=1; i<=n; i++) f[i] = (1LL * f[i-1] * D + s[i-1]) % MD; g[0] = 1; //预处理D for(int i=1; i<=n; i++) g[i] = 1LL * g[i-1] * D % MD;}int hash(int l, int r) //计算区间 [l,r] 的哈希值{ int a = f[r]; int b = 1LL * f[l-1] * g[r-l+1] % MD; return (a - b + MD) % MD; //+MD是为了防止出现负数 }int main(){ cin >> s; n = s.length(); prehash(n); while(!cin.eof())//直至按ctrl+z键退出! { int l, r; cin >> l >> r; cout << s.substr(l-1, r-l+1) << ": " << hash(l, r) << endl; //从l-1到r-l+1的字符 } return 0;}
良心推荐洛谷练手题:P3370
【模板】字符串哈希
题目描述
如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。
友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)
输入输出格式
输入格式：
第一行包含一个整数N，为字符串的个数。
接下来N行每行包含一个字符串，为所提供的字符串。
输出格式：
输出包含一行，包含一个整数，为不同的字符串个数。
输入输出样例
5abcaaaaabcabcc12345
4
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，Mi≈6，Mmax<=15;
对于70%的数据：N<=1000，Mi≈100，Mmax<=150
对于100%的数据：N<=10000，Mi≈1000，Mmax<=1500
样例说明：
样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。
Tip： 感兴趣的话，你们可以先看一看以下三题：
BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097
BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098
BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099
如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的^_^
思路:
题解里面是有很多种方法的,但是我认为能够搞懂一种就已经很不错了……所以我给出的思路就是用set来进行统计,set只能够允许一种数字出现一次,所以我们就可以将给出的字符串的hash值求出来,加入到set里面,最后直接输出set里面有多少数就行啦~
PS:定义函数的时候不要用"hash"这个名字,在洛谷里是关键字!!!
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cstring>#include <set>using namespace std;typedef unsigned long long ull;typedef long long LL;set<ull>ssr;const int N = 2333;const int D = 131; //质数 const ull MD= 1e9 + 7; //大质数 LL n,len;string s; ull f[N];//预处理前缀和 ull g[N];//预处理 D的i次方 int yuchuli(int q){ memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); f[0]=s[0]; for(int i=1;i<=q;i++) f[i] = (1LL * f[i-1] * D +s[i-1]) % MD; g[0]=1; for(int i=1;i<=q;i++) g[i] = 1LL * g[i-1] * D % MD;}int hash(int l,int r){ ull a = f[r]; ull b = 1LL * f[l-1] *g[r-l+1] % MD; return (a - b + MD) % MD;}int main(){ cin>>n; while(n--) { cin>>s; len=s.length(); yuchuli(len); ull qq = hash(1,len); ssr.insert(qq); } cout<<ssr.size(); return 0;}/*5abcaaaaabcabcc12345*/
hash 模板 x