“啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!”
一阵惨叫声响起。
“啊啊啊啊,这么长的字符串找匹配子串,完了”
Music:雨,打在脸上,冰凉,冰凉
好吧,这并不是一个恐怖故事(或者说悲惨世界翻版?),不过这一次,我们就来讲讲哈希(hash)
一,概念
hash算法主要是给一段很大的数值(也可以是很长的字符串)进行编码,然后通过编码来实现两个字符串的匹配。
差不多就像身份证号码,看一下某几位数字就知道两个人是不是同一天出生,同一个省等等
二,进制转换
要讲hash,首先要讲进制转换
在hash算法里,我们知道字符串s,将它看成b进制数,那么字符串s里每个字母都是b进制的一个符号,代表一个数值,那么相信你们也都知道了,将字符串每个字符看做一个数,然后按位权展开
三,hash匹配
这里直接配合代码讲解。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull power[1000005],mod=1e9+7,b=257,sum[1000005];
void init()//预处理b的幂
{
power[0]=1;
for(int i=1;i<=1000000;i++)
power[i]=power[i-1]*b;
}
ull c_pickstr(string s)//计算匹配串的值
{
ull sum=0;
int n=s.length();
s="#"+s;
for(int i=1;i<=n;i++)
sum=sum*b+(ull)(s[i]);//根据实际情况修改
return sum;
}
void c_mustr(string s)//母串前缀和
{
int n=s.size();
s="#"+s;
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]*b+(ull)(s[i]);
}
string c,s;
int ans;
int main()
{
cin>>c>>s;
//sum[i]表示由前i个字母组成的子串的hash值,power[i]为b的i次方
int len1=c.size(),len2=s.size();
c_mustr(c);
ull g=c_pickstr(s);
init();
for(int i=0;i<=len1-len2;i++)
if(sum[i+len2]-sum[i]*power[len2]==g) ans++;
//将sum[i]扩大到与sum[i+len2]的位数相同,才能取出正确的值
cout<<ans;
return 0;
}
这是一道求子串在母串中出现了多少次的题,这里再把题给放一下
给出两个字符串s1,s2,求s2在s1中出现多少次。
例如:s1="ABAABA",s2="ABA"答案为2。
1≤s1的长度≤10^6,1≤s2的长度≤10^4,仅包含字母。
四,b的取值
上面我们一直讲b进制,那么b到底去多少好呢?
这取决于字符串的字符范围,如果是大写字母或小写字母,那么建议b=29或b=31,如果是0到9十个数字的话,建议b=11或b=13,如果几个混搭或者有空格分号等于这些其他符号,建议将b设为263,另外,如果采用前两种的话,一定要加上s[i]-'a'+1
之类的
简单来说,就是ASCll码向上涨一些,不过得是质数
五,双哈希
在比赛场上,毒瘤出题人总会处处刁难你。
因为我们上面使用的是自然溢出(就是变量超过储存范围直接从0开始计数),但因为这个原因,我们假设ull类型最高储存的数值为mod,那么两个并不匹配的字符串的hash值分别为100和100+mod,如此一来,两个字符串就会被认定完全一样。
所以我们要用双哈希
双哈希就是使用两个hash数组来进行判断,就像用两个密码,不过要用两个mod,这里建议将第一个和第二个mod分别设置成10^9+7和10^9+9,因为它们是一对孪生素数!如果要让这个双hash错误,至少两个字符串的hash值分辨要打到100和100+(10^9+7)*(10^9+9)!
六,结语
没想到这篇比昨天的更水
有问题欢迎在讨论区提出
好活儿,当赏