算法---哈希及其在字符串中的应用（字符串hash）

哈希算法

---前言

         "加密是信息时代的锁,密码是钥匙。" - 斯科特·莱普斯基(Scott Adams)

        当今，为了信息的存储安全，密码学兴起，哈希（hash)算法也由此应运而生，哈希算法是一种加密算法，是将一个数据转换为一个标志，这个标志和源数据有十分紧密的关系。哈希 算法还有一个特点，就是很难找到逆向的规律。所以在日常的使用中，哈希算法常被用来对字符串进行压缩编码，将一段字符串转化成对应的数字或其他标志，以方便存储和比较。

---正文

        ·整数哈希（哈希介绍）

        做为竞赛算法来说，整数哈希算法经常用来存储极大的数据以起到缩小数据规模的效果，而经过哈希算法处理后的数据会被存到一个数据结构-散列表（hash表）中，其采用映射的思想，可以通过关键字在表中快速查找数据，而Hash函数的设计也层出不穷，在算法竞赛中，最常用的就是取模法，下文也以取模法为例来介绍+实现。

举个例子，对于数据5，9，18，28，16来说，如果使用hash表存储，模数为7，那么就应该为

5：5 mod 7=5，存储在下标为5处。

9：9 mod 7=2，存储在下标为2处。

18：18 mod 7=4,存储在下标为4处。

28：28 mod 7=0，存储在下标为0处。

16: 16 mod 7=2,应当存储在下标为2处。

        这时我们发现16和9的模数相同，也就是说，发生了哈希冲突，对于整数哈希冲突，也有许多不同的解决方案，此处，提供两种解决方案，开放地址法和链地址法。

开放地址法：将当前的数向后（或向其他方向，不定）挪移，直到可以存储。

链地址法：将当前的数在该下标下再拉一条链，形成一个链表，并将该数存储到链表下。

        但是显而易见，这两种办法对于解决哈希冲突并不十分有效，所以我们要尽量减少哈希冲突的情况，一般而言，将模数设为足够大的质数可以有效减少哈希冲突出现的情况。

        不过，对于整数哈希，我们一般不需要手写哈希，可以使用C++的STL库中的自带的无序map:unordered_map和无序集合：unordered_set来代替手写整数哈希，故此处不附代码，若想手写直接按照上述过程模拟即可。

        ·字符串哈希（哈希拓展）

        经过上述介绍，我们知道利用哈希函数可以很快的查询和比较，而对于字符串来说，若要比较字符串是否相等，需要逐位比较，效率显然很低，时间复杂度为O(n)，所以我们考虑使用哈希优化，而如何将字符串转成可以正常按位置比较大小的数字呢？，类比进制转换，我们把字符串看成一个128进制（ASCII码）的数字，每个字符相对应的就是其ASCII码值，再按权展开就能得到其哈希值，如abcd这个字符串，它的哈希值就是97*128^3+98*128^2+99*128^1+100*128^0,由此我们可以得到一个公式（其中hash[i]表示第1位到第i位的哈希值，base表示底数，mod表示模数,s是原字符串）：

hash[i]=(hash[i-1]*base%mod+s[i]%mod)%mod

哈希值是可以进行正常比较的，我们类比十进制来理解，一个数按权展开后就是得到的原数，其值完全可以正常比较，所以哈希值也是可以进行字符串之间的正常比较的，而且它不需要逐位比较，效率比逐位比较更高，基本为O(1)，这样就能极大程度的优化时间，使得程序不会超时。

        但是，一般来说，底数（即权值）最好要定义成一个质数（避免哈希冲突），所以一般会选择第一个比128大的质数131来做底数，不过，事实上，只要大小合理，且为质数，任何大于128的数都是一个不错的底数，但是最常用的底数仍然是131。

模板（求哈希值）

题面概括：

        给定一个字符串，求其对应的哈希值，对998244353取模。

思路：

        纯模板题，直接按上述过程模拟即可。

代码：

#includeusing namespace std;
long long has[100005];
const int mod=998244353;
int main(){
    string s;
    getline(cin,s);
    has[0]=s[0]%mod;
    for(int i=1;i 
T2.查字典
 
题面概括：
 
        给定n组单词和其翻译后的单词，然后输入q个单词，将单词翻译后输出，如果没有对应的单词则输出“eh"。
 
思路：
 
        这道题也是模板题，先把原单词转为哈希值后存储，每输入一个需要翻译的单词，就将其的哈希值求出，并与之前求出的所有原单词的哈希值做比较，如果相等，输出记录的对应的翻译后的单词即可，如果没有相等的单词则输出”eh"。
 
代码：
 
#includeusing namespace std;
long long has[1005];
const int mod=998244353;
string k[1005];
int main(){
    int n,q;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k[i]>>s;
        int len=s.size();
        for(int j=0;j>q;
    for(int i=1;i<=q;i++){
        cin>>s;
        int sum=0;
        int len=s.size();
        for(int j=0;j 
T3.消失的密文
 
———————————————————————————————————————————
 
前置知识：
 
        对于一个已经求得下标从1开始所有长度哈希值的字符串来说，如何求它的子串呢？，我们考虑将哈希值当成前缀和的形式来求得，那么如果要求l~r这段子串的哈希值，是用hash[r]-hash[l-1]吗？答案是否定的，因为，hash[l-1]比hash[r]少乘了r-l+1个base(底数），导致指数无法对齐，所以我们就可以得到正确的公式（hash(l，r)表示l~r这段子串的哈希值,p[i]表示底数的i次方）:
 
 
hash(l,r)=(hash[r]-(hash[l-1]*p[r-l+1])%mod+mod)%mod
 
 
———————————————————————————————————————————
 
题面概括：
 
        给定一个密码表S，S[i]表示第i个小写字母解密后对应的字母（下标由1开始），然后给出一条密文K，密文的末尾缺失了一部分单词，而完整密文的前半段是密文，后半段是解密后的”明文“，要求求出最短的完整的密文。
 
思路：
 
        这道题的难点，也是中心，就在于如何确定给出的密文中哪部分是密文，那部分是“明文”，也就是完整密文的中点位置，对于这道题来说，密文不是很长，所以可以使用枚举的方法来枚举中点，先用hash数组记录哈希值,再枚举中点k,取最前面n-k个字符的哈希值和k后面n-k个字符的哈希值（先将面n-k个字符转为明文后）作比较，如果两者相等就说明k是最小的中点，直接跳出循环并输出前k个密文和后k个明文即可。
 
代码：
 
#includeusing namespace std;
long long has[100005],p[100005],mhas[100005];
const int mod=998244353;
long long mid;
map ma,pma;
int main(){
    int n;
    string s,b;
    cin>>n;
    for(int i=1;i<=n;i++){
    	ma.clear();
    	pma.clear();
        memset(has,0,sizeof has);
        memset(mhas,0,sizeof mhas);
        cin>>s>>b;
        b=' '+b;
        s=' '+s;
        for(int i=1;i<=s.size();i++){
        	ma['a'-1+i]=s[i];
        	pma[s[i]]='a'-1+i;
		}
        int len=b.size();
        len-=1;
        p[1]=1;
        for(int j=2;j<=len;j++){
            p[j]=p[j-1]*128;
        }
        for(int j=1;j<=len;j++){
            if(j==len){
                has[j]=has[j-1]+(long long)b[j];
                mhas[j]=mhas[j-1]+(long long)ma[b[j]];
            }
            has[j]=(has[j-1]+(long long)b[j])*128;
            mhas[j]=(mhas[j-1]+(long long)ma[b[j]])*128;
        }
        for(int j=(len+1)/2;j<=len;j++){
            long long hh=mhas[len]-mhas[j-1]*p[len-(j-1)+1];
            if(has[len-j+1]==hh){
                mid=j;
                break;
            }
        }
		for(int j=1;j 
T4.不同子串（双哈希）
 
———————————————————————————————————————————
 
前置知识：
 
        整数哈希中最重要的问题便是哈希冲突，而在字符串哈希中同样如此，由于字符串哈希的局特殊性，我们无法使用一些在整数哈希中使用的方法来解决哈希冲突，所以我们主要来通过方法使得哈希冲突的概率降到一个极其微小的地步，这里介绍一个方法：双哈希，顾名思义，就是对同一个字符串，使用两个底数不同且模数不同的哈希函数分别求值，在判断时要求两个哈希函数的值必须都一一对应才能判断两个字符串相等，这样能令哈希冲突基本不可能出现。
 
———————————————————————————————————————————
 
 题面概括：
 
        给出一个字符串S，求这个字符串中有多少长度不同的子串。
 
思路：
 
        这道题是一道经典的哈希例题，但是如果直接使用单哈希会被卡数据，所以考虑使用双哈希，与上一题相同，这道题也是枚举所有字串开头的字符下标位置（也可以是结尾字符下标位置），然后对没有出现的哈希值进行记录，并累加，最后累加的值即为答案，输出即可，注意，在记录和判断时要使用pair，否则会出现数据不对应导致答案错误。
 
代码：
 
//双哈希 
#includeusing namespace std;
long long hasa[1000005],hasb[1000005],p[1000005],p1[1000005];
const int mod=1e9+7,modb=998244353;
const int base=131,base1=128;
map,int> ma;
int main(){
    string s;
	int n,l;
	cin>>n>>l;
	cin>>s;
	s=' '+s;
	int len=s.size();
	len-=1;
	p[0]=p1[0]=1;
	for(int i=1;i<=len;i++){
	    p[i]=p[i-1]*base%mod;
	    p1[i]=p1[i-1]*base1%modb;
	}
	for(int i=1;i<=len;i++){
	    hasa[i]=((hasa[i-1]*base)%mod+(long long)s[i]%mod)%mod;
	    hasb[i]=((hasb[i-1]*base1)%modb+(long long)s[i]%modb)%modb;
	}
	long long cnt=0;
	for(int i=l;i<=len;i++){
	    long long xx=hasa[i]-hasa[i-l]*p[l]%mod;
	    long long yy=hasb[i]-hasb[i-l]*p1[l]%modb;
	    //cout<