转载地址
Hash 是什么意思呢? 某度翻译告诉我们:
hash 英[hæ?] 美[hæ?]
n. 剁碎的食物; #号; 蔬菜肉丁;
vt. 把弄乱; 切碎; 反复推敲; 搞糟;
我觉得 Hash 是引申出 把... 弄乱 的意思
今天就来谈谈 Hash 的一种字符串 hash
据我的理解, Hash 就是一个像函数一样的东西, 你放进去一个值, 它给你输出来一个值输出的值就是 Hash 值一般 Hash 值会比原来的值更好储存 (更小) 或比较
那字符串 Hash 就非常好理解了就是把字符串转换成一个整数的函数而且要尽量做到使字符串对应唯一的 Hash 值
字符串 Hash 的种类还是有很多种的, 不过在信息学竞赛中只会用到一种名为 BKDR Hash 的字符串 Hash 算法
它的主要思路是选取恰当的进制, 可以把字符串中的字符看成一个大数字中的每一位数字, 不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是
O(n)
的), 但只要把它对一个数取模, 然后认为取模后的结果相等原数就相等, 那么就可以在一定的错误率的基础上
O(1)
进行判断了
那么我们选择什么进制比较好?
首先不要把任意字符对应到数字 0, 比如假如把 a 对应到数字 0, 那么将不能只从 Hash 结果上区分 ab 和 b(虽然可以额外判断字符串长度, 但不把任意字符对应到数字 0 更加省事且没有任何副作用), 一般而言, 把 a-z 对应到数字 1-26 比较合适
关于进制的选择实际上非常自由, 大于所有字符对应的数字的最大值, 不要含有模数的质因子(那还模什么), 比如一个字符集是 a 到 z 的题目, 选择 2723319260817 都是可以的
模数的选择(尽量还是要选择质数):
绝大多数情况下, 不要选择一个
109
级别的数, 因为这样随机数据都会有 Hash 冲突, 根据生日悖论, 随便找上
10
9
个串就有大概率出现至少一对 Hash 值相等的串(参见 BZOJ 3098 Hash Killer II)
最稳妥的办法是选择两个
109
级别的质数, 只有模这两个数都相等才判断相等, 但常数略大, 代码相对难写, 目前暂时没有办法卡掉这种写法(除了卡时间让它超时)(参见 BZOJ 3099 Hash Killer III)
如果能背过或在考场上找出一个
1018
级别的质数(Miller-Rabin), 也相对靠谱, 主要用于前一种担心会超时, 后一种担心被卡
偷懒的写法就是直接使用 unsigned long long, 不手动进行取模, 它溢出时会自动对
264
进行取模, 如果出题人比较良心, 这种做法也不会被卡, 但这个是完全可以卡的, 卡的方法参见 BZOJ 3097 Hash Killer I
用 luogu P3370 为例
这是自然溢出 hash(100)
- C++
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef unsigned long long ull;
- ull base=131;
- ull a[10010];
- char s[10010];
- int n,ans=1;
- ull hashs(char s[])
- {
- int len=strlen(s);
- ull ans=0;
- for (int i=0;i<len;i++)
- ans=ans*base+(ull)s[i];
- return ans&0x7fffffff;
- }
- main()
- {
- scanf("%d",&n);
- for (int i=1;i<=n;i++)
- {
- scanf("%s",s);
- a[i]=hashs(s);
- }
- sort(a+1,a+n+1);
- for (int i=2;i<=n;i++)
- if (a[i]!=a[i-1])
- ans++;
- printf("%d\n",ans);
- }
这是单模数 hash(80)
- C++
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef unsigned long long ull;
- ull base=131;
- ull a[10010];
- char s[10010];
- int n,ans=1;
- ull mod=19260817;
- ull hashs(char s[])
- {
- int len=strlen(s);
- ull ans=0;
- for (int i=0;i<len;i++)
- ans=(ans*base+(ull)s[i])%mod;
- return ans;
- }
- main()
- {
- scanf("%d",&n);
- for (int i=1;i<=n;i++)
- {
- scanf("%s",s);
- a[i]=hashs(s);
- }
- sort(a+1,a+n+1);
- for (int i=2;i<=n;i++)
- if (a[i]!=a[i-1])
- ans++;
- printf("%d\n",ans);
- }
这是双 hash(100)
- C++
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef unsigned long long ull;
- ull base=131;
- struct data
- {
- ull x,y;
- }a[10010];
- char s[10010];
- int n,ans=1;
- ull mod1=19260817;
- ull mod2=19660813;
- ull hash1(char s[])
- {
- int len=strlen(s);
- ull ans=0;
- for (int i=0;i<len;i++)
- ans=(ans*base+(ull)s[i])%mod1;
- return ans;
- }
- ull hash2(char s[])
- {
- int len=strlen(s);
- ull ans=0;
- for (int i=0;i<len;i++)
- ans=(ans*base+(ull)s[i])%mod2;
- return ans;
- }
- bool comp(data a,data b)
- {
- return a.x<b.x;
- }
- main()
- {
- scanf("%d",&n);
- for (int i=1;i<=n;i++)
- {
- scanf("%s",s);
- a[i].x=hash1(s);
- a[i].y=hash2(s);
- }
- sort(a+1,a+n+1,comp);
- for (int i=2;i<=n;i++)
- if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
- ans++;
- printf("%d\n",ans);
- }
这是只用一个 10^18 质数的 hash(100)
- C++
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef unsigned long long ull;
- ull base=131;
- ull a[10010];
- char s[10010];
- int n,ans=1;
- ull mod=212370440130137957ll;
- ull hashs(char s[])
- {
- int len=strlen(s);
- ull ans=0;
- for (int i=0;i<len;i++)
- ans=(ans*base+(ull)s[i])%mod;
- return ans;
- }
- main()
- {
- scanf("%d",&n);
- for (int i=1;i<=n;i++)
- {
- scanf("%s",s);
- a[i]=hashs(s);
- }
- sort(a+1,a+n+1);
- for (int i=2;i<=n;i++)
- if (a[i]!=a[i-1])
- ans++;
- printf("%d\n",ans);
- }
Hash 还有一方面, 就是它可以处理子串信息对于一个字符串, 我们可以预处理它
1l
的 hash 值, 这样
l+1
的 hash 值就可以
O(1)
的递推出来
对于一个字符串
lr
的子串, 我们可以用
f[r]
brl
来求出来, 其中 b 表示进制
这样的话 hash 就可以水过字符串匹配的题目
cogs1570
题目描述
法国作家乔治. 佩雷克 (Georges Perec,1936-1982) 曾经写过一本书, 敏感字母 (La disparition), 全篇没有一个字母 e 他是乌力波小组(Oulipo Group) 的一员下面是他书中的一段话:
Tout avait Pair normal, mais tout saffirmait faux. Tout avait Fair normal, dabord, puis surgissait linhumain, laffolant. Il aurait voulu savoir où sarticulait lassociation qui lunissait au roman : stir son tapis, assaillant à tout instant son imagination, lintuition dun tabou, la vision dun mal obscur, dun quoi vacant, dun non-dit : la vision, lavision dun oubli commandant tout, où sabolissait la raison : tout avait lair normal mais
佩雷克很可能在下面的比赛中得到高分 (当然, 也有可能是低分) 在这个比赛中, 人们被要求针对一个主题写出甚至是意味深长的文章, 并且让一个给定的单词出现次数尽量少我们的任务是给评委会编写一个程序来数单词出现了几次, 用以得出参赛者最终的排名参赛者经常会写一长串废话, 例如 500000 个连续的 T 并且他们不用空格
因此我们想要尽快找到一个单词出现的频数, 即一个给定的字符串在文章中出现了几次更加正式地, 给出字母表 {A,B,C,...,Z} 和两个仅有字母表中字母组成的有限字符串: 单词 W 和文章 T, 找到 W 在 T 中出现的次数这里出现意味着 W 中所有的连续字符都必须对应 T 中的连续字符 T 中出现的两个 W 可能会部分重叠
输入格式
输入包含多组数据
输入文件的第一行有一个整数, 代表数据组数接下来是这些数据, 以如下格式给出:
第一行是单词 W, 一个由 {A,B,C,...,Z} 中字母组成的字符串, 保证 1<=|W|<=10000(|W | 代表字符串 W 的长度)
第二行是文章 T, 一个由 {A,B,C,...,Z} 中字母组成的字符串, 保证 | W|<=|T|<=1000000
输出格式
对每组数据输出一行一个整数, 即 W 在 T 中出现的次数
样例输入
- 3
- BAPC
- BAPC
- AZA
- AZAZAZA
- VERDI
- AVERDXIVYERDIAN
样例输出
1
3
0
代码
- C++
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef unsigned long long ull;
- ull base=131;
- ull po[100010],hs[100010*100];
- char s1[100010],s2[100010*100];
- int n,ans=1,T;
- ull geth(int l,int r)
- {
- return (ull)hs[r]-po[r-l+1]*hs[l-1];
- }
- main()
- {
- freopen("oulipo.in","r",stdin);
- freopen("oulipo.out","w",stdout);
- po[0]=1;
- for (int i=1;i<=10010-5;i++)
- po[i]=po[i-1]*base;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%s%s",s1+1,s2+1);
- int l1=strlen(s1+1),l2=strlen(s2+1);
- ull a1=0,ans=0;
- for (int i=1;i<=l1;i++)
- a1=a1*base+(ull)s1[i];
- for (int i=1;i<=l2;i++)
- hs[i]=hs[i-1]*base+s2[i];
- for (int i=1;i+l1-1<=l2;i++)
- if (a1==geth(i,i+l1-1))
- ans++;
- printf("%d\n",ans);
- }
- }
写到这里突然发现 hash 好像可以暴力水过很多字符串算法
1kmp
问题: 给两个字符串 S1,S2, 求 S2 是否是 S1 的子串, 并求 S2 在 S1 中出现的次数
把 S2 Hash 出来, 在 S1 里找所有长度为
|
S2|
的子串, Hash 比较效率
O
(
|
S1|)
2AC 自动机
问题: 给 N 个单词串, 和一个文章串, 求每个单词串是否是文章串的子串, 并求每个单词在文章中出现的次数
把每一个单词 hash 成整数, 再把文章的每一个子串 hash 成整数, 接下来只需要进行整数上的查找即可
复杂度:
- O
- (
- |
- A
- |
- 2+|S|)
用 AC 自动机可以做到
- O
- (
- |
- A
- |
- +
- |
- S|)
的复杂度,
|
S|
是单词串总长,
|A|
是文章长度
3 后缀数组
问题: 给两个字符串 S1,S2, 求它们的最长公共子串的长度
将 S1 的每一个子串都 hash 成一个整数, 将 S2 的每一个子串都 hash 成一个整数
两堆整数, 相同的配对, 并且找到所表示的字符串长度最大的即可
复杂度:
- O
- (
- |
- S
- 1
- |
- 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 真是一种优雅的暴力
因为字符串特殊的性质, 我们可以二分得处理它, 一般都有单调性
来源: http://www.bubuko.com/infodetail-2514795.html