字符串哈希算法详解

fedoralxy · 2023-11-30 10:36:09 · 算法·理论

字符串哈希算法详解

• 引入

  我们要解决这样一个问题：

  给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母。

  A 中不同位置出现的 B 可重叠。

  那么，我们很容易想到这样一个解决方案： ```cpp #include<iostream> #include<cstdio> using namespace std; const int N=1e4+5; int s[N]; int main() { int cnt=0; string a,b; cin>>b>>a; s[0]=0; for(int i=1;i<a.size();i++) { int j=s[i-1]; while(j&&a[j]!=a[i]) j=s[j]; if(a[j]==a[i]) j++; s[i]=j; } int j=0; for(int i=0;i<b.size();i++) { while(j>0&&a[j]!=b[i]) j=s[j]; if(a[j]==b[i]) ++j; if(j==a.size()-1) cnt++,j=s[j]; } cout<<cnt; return 0; } ```

但是很显然，这个方法在时间复杂度方面是不能接受的。

• 哈希思想

  那么我们就要使用一个哈希思想：

  哈希的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

  这么说可能不太好理解，其实哈希就是给每一个字符串一个编号，如果两个字符串编号相同那么这两个字符串就相同。

• 性质

  具体来说，哈希函数最重要的性质可以概括为下面两条：

  1. 在哈希函数值不一样的时候，两个字符串一定不一样；

  2. 在哈希函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

  我们将哈希函数值一样但原字符串不一样的现象称为哈希碰撞。

  从概率学的角度来说“小概率事件不会发生”，就比如一件事情发生的可能性是一千万亿分之一，甚至无限趋于零，那我们就说这件事不会发生，哈希碰撞就是如此。

• 哈希函数的定义

  一般，我们这样定义哈希函数：

  f(s)=\sum^{l}_{i=1}s[i] \times b^{l-i} (modM)

  例如，对于字符串 xyz 的哈希函数值为 xb^2+yb+z。

  当然也可以反着定义：

  f(s)=\sum^{l}_{i=1}s[i] \times b^{i-1} (modM)

  也就是 xyz 的函数值为 x+yb+z^2。

  由于前者的计算更加简便，所以在大多数情况下大多人都会使用前者的方法来定义哈希函数。

• 哈希碰撞的概率（哈希的准确率）

  这里其实是一个哈希准确率的论述过程，可以选择性阅读。

  这里 M 需要选择一个素数（至少要比最大的字符要大），b 可以任意选择。

  如果我们用未知数 x 替代 b ，那么 f(s) 实际上是多项式环 \mathbb{Z}_M[x] 上的一个多项式。

  考虑两个不同的字符串 s,t，有 f(s)=f(t)。

  我们记:

  h(x)=f(s)-f(t)=\sum_{i=1}^l(s[i]-t[i])x^{l-i}\pmod M

  其中 l=\max(|s|,|t|)

  可以发现 h(x) 是一个 l-1 阶的非零多项式。

  如果 s 与 t 在 x=b 的情况下哈希碰撞，则 b 是 h(x) 的一个根。由于 h(x) 在 \mathbb{Z}_M 是一个域（等价于 M 是一个素数，这也是为什么 M 要选择素数的原因）的时候，最多有 l-1 个根，如果我们保证 b 是从 [0,M) 之间均匀随机选取的，那么 f(s) 与 f(t) 碰撞的概率可以估计为 \frac{l-1}{M}。

  验算一下，可以发现如果两个字符串长度都是 1 的时候，哈希碰撞的概率为 \frac{1-1}{M}=0，此时不可能发生碰撞。

  (参考自OI-WIKI)

• 实现

  对于一开始的问题，根据上面的学习，我们得出了一个新的解决方案。

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  #define ull unsigned long long
  using namespace std;
  const int N=1e6+10;
  ull h[N],hs=0;
  char s[N],t[N];
  ull qp(ull x,ull y)
  {
    ull now=x,ans=1;
    while(y)
    {
        if(y&1)
            ans*=now;
        now*=now;
        y>>=1;
    }
    return ans;
  }
  int main()
  {
    cin>>s+1>>t+1;
    int l1=strlen(s+1),l2=strlen(t+1);
    for(int i=1;i<=l1;++i)
        h[i] = h[i-1]*131ull+s[i];
    for(int i=1;i<=l2;++i)
        hs = hs*131ull+t[i];
    int ans=0;
    for(int i=l2;i<=l1;++i)
    {
        ull now=h[i]-h[i-l2]*qp(131,l2);
        if(now==hs)
            ans++;
    } 
    cout<<ans<<endl;
    return 0;
  }

• 练习

#10033 「一本通 2.1 例 1」Oulipo

#10034 「一本通 2.1 例 2」图书管理

#10035 「一本通 2.1 练习 1」Power Strings

#10036 「一本通 2.1 练习 2」Seek the Name, Seek the Fame

#10037 「一本通 2.1 练习 3」Friends

#10038 「一本通 2.1 练习 4」A Horrible Poem

#10039 「一本通 2.1 练习 5」Beads

#10040 「一本通 2.1 练习 6」Antisymmetry

#10041 「一本通 2.1 练习 7」门票

#10042 「一本通 2.1 练习 8」收集雪花