字符串hash入门

简单介绍一下字符串hash

相信大家对于hash都不陌生

hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法

在信息学奥赛中,hash算法主要应用于搜索状态判重,字符串的比较等

hash的主要思想是:对于一个空间、时间需求较大的状态,在一定错误率的基础上进行状态压缩,降低其时间、空间的需求量

对于字符串hash来说,就是把一串字符串压缩成一个hash值,方便我们进行数据的处理

接下来我们重点讲一下字符串hash的实现方法

实现方法

思想

在信息学奥赛中,使用最广泛的算法叫做:BKDR Hash

它的核心思想是:

对于一个字符串,选取恰当的进制,将一个字符串看做是一个大整数 (众人:***,你这是要让我们写高精啊) 然后再对一个随便什么数取模就可以啦

当然这个“恰当的进制”和“随便什么数”是有讲究的

根据砖家的研究:

进制一般选择大于字符串中的最大的字符且不含模数的值因子的数

比如说,如果你是对一串小写字母做字符串hash,那么131这个进制就是不错的选择

而“随便什么数”有三种方法

  1. 选择两个模数,判断的时候只有两个hash值都相同才算相同
  2. 选择一个大质数,像11111111111111111111111或者212370440130137957
  3. 用unsigned long long 自然溢出

注意:尽量不要只用一个较小的质数,根据生日悖论,很容易被卡

代码

代码实现比较简单

https://www.luogu.org/problemnew/show/3370

  • unsigned long long 自然溢出
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<map>
 8 #define lli long long int 
 9 using namespace std;
10 const int MAXN=100001;
11 int seed=27;
12 void read(int &n)
13 {
14     char c='+';int x=0;bool flag=0;
15     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
16     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
17     n=flag==1?-x:x;
18 }
19 char a[MAXN];
20 map<long long ,bool>happen;
21 int tot=0;
22 int main()
23 {
24     int n;
25     read(n);
26     for(int i=1;i<=n;i++)
27     {
28         unsigned long long base=1;
29         scanf("%s",a);
30         for(int j=0;j<strlen(a);j++)
31             base=base*seed+(a[j]);
32         if(!happen[base])
33             happen[base]=1,tot++;
34     }
35     printf("%d",tot);
36     return 0;
37 }
  • 双hash
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ull unsigned long long 
 5 using namespace std;
 6 const int MAXN=2e7+10;
 7 const int mod1=19260817;
 8 const int mod2=19660813;
 9 const int seed=233;
10 const int seed2=133;
11 int n;
12 struct node
13 {
14     char s[1501];
15     int h1,h2,l;
16 }a[10001];
17 ull gethash1(char *s,int l)
18 {
19     ull ans=0;
20     for(int i=1;i<=l;i++)
21         ans=(ans*seed+(ull)s[i])%mod1;
22     return ans;
23         
24 }
25 ull gethash2(char *s,int l)
26 {
27     ull ans=0;
28     for(int i=1;i<=l;i++)
29         ans=(ans*seed2+(ull)s[i])%mod2;
30     return ans;
31 }
32 int hash1[MAXN],hash2[MAXN];
33 int main()
34 {
35     scanf("%d",&n);
36     for(int i=1;i<=n;i++)
37     {
38         scanf("%s",a[i].s+1);
39         a[i].l=strlen(a[i].s+1);
40     }
41     for(int i=1;i<=n;i++)
42     {
43         a[i].h1=gethash1(a[i].s,a[i].l)%mod1;
44         a[i].h2=gethash2(a[i].s,a[i].l)%mod2;
45     }
46     int ans=0;
47     for(int i=1;i<=n;i++)
48         if(hash1[a[i].h1]==0||hash2[a[i].h2]==0)
49             hash1[a[i].h1]=1,hash2[a[i].h2]=1,ans++;
50     printf("%d",ans);
51     return 0;
52 }
  • 大质数hash
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<map>
 8 #define lli long long int 
 9 using namespace std;
10 const int MAXN=100001;
11 const long long int mod=212370440130137957;
12 int seed=27;
13 void read(int &n)
14 {
15     char c='+';int x=0;bool flag=0;
16     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
17     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
18     n=flag==1?-x:x;
19 }
20 char a[MAXN];
21 map<int,bool>happen;
22 int tot=0;
23 int main()
24 {
25     int n;
26     read(n);
27     for(int i=1;i<=n;i++)
28     {
29         long long base=1;
30         scanf("%s",a);
31         int la=strlen(a);
32         for(int j=0;j<la;j++)
33             base=(base*seed+(a[j]) )%mod;
34         if(!happen[base])
35             happen[base]=1,tot++;
36     }
37     printf("%d",tot);
38     return 0;
39 }

特别注意:在循环的时候,不要写: for(int j=0;j<strlen(a);j++) !!!!因为strlen的复杂度是O(n^2),数据稍微一大你就会被卡T

正确的姿势是把长度记录下来 int la=strlen(a); for(int j=0;j<la;j++)

常用技巧:区间hash值

在进行字符串hash的时候,我们经常会用到某一段的hash值

这时候怎么办呢?

假设我们已经得到了hash[1-r]

那么hash[l-r]=hash[r]-seed^{r-l+1}*hash[l](seed表示进制)

举个例子

hash[1]=a1

hash[2]=a1*base+a_2

hash[3]=(a_1*seed+a_2)*seed+a_3=a_1*seed^2+a_2*seed+a_3

hash[4]=[(a[1*seed+a_2)*seed+a_3]*seed+a_4=a1*seed^3+a2*seed^2+a_3*seed+a_4

hash[3-4]=hash[4]-(4-3+1)^2*hash[2]=a_3*seed+a_4

很明显可以看出这个公式是对的

最好自己手写一下,这样才能体会到其中的奥妙

经典题目

洛谷 P3370 【模板】字符串哈希  

必做练手题,代码已经在上面给出了

洛谷 P3375 【模板】KMP字符串匹配

这道题可以用字符串hash水过

http://www.cnblogs.com/zwfymqz/p/7793347.html

洛谷P2264 情书

这道题理论上是可以用字符串hash做的

但是我只水到90分,各位神犇可以尝试一下

http://www.cnblogs.com/zwfymqz/p/7355159.html

BZOJ 3555: [Ctsc2014]企鹅QQ

 略有难度

http://www.cnblogs.com/zwfymqz/p/7349658.html

洛谷P3823 蚯蚓排队

其他经典应用

以下内容来自远航之曲大神,在此表示衷心的感谢

1、kmp 问题:给两个字符串S1,S2,求S2是否是S1的子串,并求S2在S1中出现的次数 把S2 Hash出来,在S1里找所有长度为|S2|的子串,Hash比较。效率O(|S1|) 2、AC自动机 问题:给N个单词串,和一个文章串,求每个单词串是否是文章串的子串,并求每个单词在文章中出现的次数。 把每一个单词hash成整数,再把文章的每一个子串hash成整数,接下来只需要进行整数上的查找即可。 复杂度:O(|A|2+|S|) 用AC自动机可以做到O(|A|+|S|)的复杂度,|S|是单词串总长|A|是文章长度 3、后缀数组 问题:给两个字符串S1,S2,求它们的最长公共子串的长度。 将S1的每一个子串都hash成一个整数,将S2的每一个子串都hash成一个整数 两堆整数,相同的配对,并且找到所表示的字符串长度最大的即可。 复杂度:O(|S1|2+|S2|2) 用后缀数组可以优化到O(|S|log|S|) 4、马拉车 问题:给一个字符串S,求S的最长回文子串。 先求子串长度位奇数的,再求偶数的。枚举回文子串的中心位置,然后二分子串的长度,直到找到一个该位置的最长回文子串,不断维护长度最大值即可。 复杂度:O(|S|log|S|) 用manacher可以做到O(|S|)的复杂度 5、扩展kmp 问题:给一个字符串S,求S的每个后缀与S的最长公共前缀 枚举每一个后缀的起始位置,二分长度,求出每个后缀与S的最长公共前缀。 复杂度:O(|S|log|S|) 用extend-kmp可以做到O(|S|)的复杂度

总结

字符串hash是一个非常优秀的算法。

希望大家能够熟练的掌握&&运用

说不定它可以在你写不出正解的时候帮你得很多分呢?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

机器学习之线性回归:OLS 无偏估计及相关性python分析

0 回顾 在最近的推送中,先后总结了最小二乘法的原理,两个求解方法:直接法和梯度下降,最后利用这两种思路进行了python实战。在用直接法求出权重参数时,有一...

48640
来自专栏智能算法

程序化广告交易中的点击率预估

指标 广告点击率预估是程序化广告交易框架的非常重要的组件,点击率预估主要有两个层次的指标: 1. 排序指标。排序指标是最基本的指标,它决定了我们有...

34860
来自专栏架构师小秘圈

面试官最讨厌的三种求职者

职场人士在职业职业生涯中一定会面临求职和面试,想要面试过关需要三个条件:职业技能达标、问题回答得体、不犯致命错误。前两点很好理解,我们来看看第三个,面试过程中...

37460
来自专栏架构师小秘圈

2017的金秋,派卧底去阿里、京东、美团、滴滴带回来的面试题及答案

最近有很多朋友去目前主流的大型互联网公司面试(阿里巴巴、京东、美团、滴滴),面试回来之后会发给我一些面试题。有些朋友轻松过关,拿到offer,但是有一些是来询问...

38860
来自专栏架构师小秘圈

Zookeeper极简教程

一、分布式协调技术 在给大家介绍ZooKeeper之前先来给大家介绍一种技术——分布式协调技术。那么什么是分布式协调技术?那么我来告诉大家,其实分布式协调技术 ...

41970
来自专栏算法channel

「动态规划后篇」:考量适用指标

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

34440
来自专栏智能算法

推荐算法概览

原文:Overview of Recommender Algorithms 作者: MAYA.HRISTAKEVA 译者: 孙薇 推荐算法概览(一) 为推...

53580
来自专栏智能算法

各大公司广泛使用的在线学习算法FTRL详解

现在做在线学习和CTR常常会用到逻辑回归( Logistic Regression),而传统的批量(batch)算法无法有效地处理超大规模的数据集和在线数据流,...

81060
来自专栏杨熹的专栏

什么是神经网络

本文结构: 什么是神经网络 什么是神经元 神经网络的计算和训练 代码实现 ---- 1. 什么是神经网络 神经网络就是按照一定规则将多个神经元连接起来的网络 例...

34850
来自专栏算法channel

机器学习高斯混合模型(后篇):GMM求解完整代码实现

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

58350

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励