浅谈字符串hash

字符串哈希作为字符串算法的入门算法除了暴力，在很多题目中都有涉及，当你遇到不会的字符串题目时，用哈希加乱搞也许就能AC。

所以今天我们来一起学习hash算法不要问我为什么中文和英文混用

首先我们来看一看hash的基本原理：

hash是通过一个函数来将一个字符串转化成一个变量，并确保其大概有唯一性。

哈希通常用于字符串匹配问题，当两个字符串或子串的哈希相等时，就大概可以确定两个串匹配（因为哈希值有可能重复，不过几率很小）

然后我们再来看hash的过程（详解）：

step1:

选定一个哈希基数S，这个数被用来在计算中扩大两个字符串的所计算出来的值的差距，避免出现重复的值，导致匹配出现错误。

step2:

计算hash值，我们将字符串的每一位拆分，并通过公式计算，设字符串C的哈希值为hash(C),其中的每个字符为c1,c2,c3……cn

hash(C) = (c1*S^n-1+c2*S^n-2+……cn*S^0)%mod

注意事项：最后的取模是很重要的，可以选择自然溢出，但容易被卡，在选数之前，可以先去洗一下脸，避免脸太黑。

step3:

对比两个 hash值如果不会的话可以洗洗睡了

举个栗子：

两个字符串: C1：ABCDE C2：ABCDF

我们定义 A=1 B=2 C=3 D=4 E=5 F=6 S=2

hash(C1)=1*2^4+2*2^3+3*2^2+4*2^1+5*2^0=57

hshh(C2)=1*2^4+2*2^3+3*2^2+4*2^1+6*2^0=58

因为hash(C1)=hash(C2),所以字符串C1与C2匹配

但是此时如果再来一个字符串

C3：BBABC

则hash(C3)=2*2^4+2*2^3+2*2^2+1*2^1+2*2^0=57

于是此时hash（C1）=hash（C2）

但很显然这两个字符串时不匹配的如果你觉得匹配，可以先去口腔医院看看脑子

这就是字符串hash的偶然性，不过如果基数S选的足够好，就可以在很大程度上避免这种情况

滚动哈希

好的，那么明眼的同学因该发现了，这个算法的的时间复杂度应该是O(n)的，和暴力一样，而且还多几个常数，这不就体现不出来它的优势了吗？

但是不要着急，聪明的人们为了改进这个算法，创造出了滚动哈希，用于完成同一个字符串的多次匹配，下面我来讲解这个算法的具体流程。

首先，我们定义一个数组，叫做ha[lenth.C]，记住，数组名称最好不要叫做hash，因为这是一些编译器中的关键词（深受其害）。

然后我们可以求出类似于前缀和的东西，我们定义ha[i]=（前i个字符的hash值）

例如：ABCDE S=2;

ha[1]=1*2^0=1;

ha[2]=1*2^1+1*2^0=4;

……………………

基于此式，我们可以得到一个公式 ha[i]=ha[i-1]*S+ci

我们还有一个问题，那就是如何求出一个字符串中间一段的hash值，我们总不能再求一遍吧，那这个算法也太弱鸡了吧。

好在我们有一个方法可以在O(1)的时间复杂内求出字符串中任意一段的hash值

我们再来一发例子： C： ABCDE S=2

定义 A=1 B=2 C=3 D=4 E=5

求 Cx：CDE 的hash值

我们知道 hash(Cx)=3*2^2+4*2^1+5*2^0=25

而ha[5]=57

ha[2]=4;

则hash（Cx）=57-4*2^3=25

登的登登，怎么样，是不是很神奇不是

但是我们怎么证明这个算法的正确性呢，跟我看推导过程：

（1）我们已知要求的串的长度L

（2）知道这个串的起始位置k

（3） ha[k+L-1]=c1*S^n-1+c2*S^n-2+……c(k+L-1)*S^0

（4） ha[k-1(下标一定要-1，因为ck被包含在字符串中)]=c1*S^n-1+c2*S^n-2+……ck*S^0

（5） hash（Cx）=cx1*S^L-1+cx2*S^L-2+……cxL*S^0

（6）可以求出ha[k-1]*S^L=ha[k+L-1]-hash(Cx)

（7）化简后可以得出 hash(Cx)=ha[k+L-1]-ha[k-1]*S^L

下面给出字符串哈希的完整代码

poj3461

给出两个串，S1，S2，求出S1在S2中出现了多少次。

输入T组数据。

友情样例:

input:

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

output:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef unsigned long long Ull;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
inline int rd()
{
    int x=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
Ull base=14541;//选定基数 
Ull po[1000005],hash[1000005];
char a[1000005],b[1000005];
Ull geth(int l,int r)//两个坐标点，计算hash值 
{
    return (Ull)hash[r]-hash[l-1]*po[r-l+1];
}
int main()
{
    po[0]=1;
    int i,j,k;
    for(i=1;i<=1000005;i++)//预处理出基数的次方 
    {
        po[i]=po[i-1]*base; 
    }
    int T;
    T=rd();
    while(T--)
    {
        scanf("%s%s",a+1,b+1);//下标从一开始 
        int h1=strlen(a+1),h2=strlen(b+1);
        Ull a1=0,ans=0;
        for(i=1;i<=h1;i++){//求出S1的hash值 
            a1*=base;
            a1+=(Ull)a[i];
        }
        for(i=1;i<=h2;i++)//构建S2的ha数组 
        {
            hash[i]=hash[i-1]*base+(Ull)b[i];
        }
        for(i=1;i+h1-1<=h2;i++)//暴力枚举下标 
        {
            if(a1==geth(i,i+h1-1))//判断是否匹配 
            {
                ans++;
            }
        }
        write(ans);//输出结果 
        puts("");
    }
    return 0;
}

最后喜欢的话不如来推荐，评论，关注三连。

不喜欢的话也昧着良心推荐一下吧！！！！

蒟蒻总是更懂你✿✿ヽ(°▽°)ノ✿

浅谈 字符串hash

浅谈字符串hash