字符串Hash学习笔记

字符串Hash学习笔记"/>

字符串Hash学习笔记

• 哈希算法

  哈希算法是通过一个哈希函数 H H H，将一种数据（包括字符串、较大的数等）转化为能够用变量表示或是直接就可作为数组下标的数。

• 哈希值

  通过哈希函数转化的得到的数值。可以通过哈希值实现快速查找和匹配。

简介

寻找长度为 n n n 的主串 S S S 中的匹配串 T T T（长度为 m m m）出现的位置或次数的问题属于字符串匹配问题。

朴素的想法是枚举所有起始位置，再直接检查是否匹配。

可以不使用 O ( m ) O(m) O(m) 的直接比较字符串的方法，而是比较长度为 m m m 的主串 S S S 的子串的哈希值是否相等，这就是哈希算法的原理——字符串 Hash。

流程

所以我们需要用到一个叫做滚动哈希的优化技巧。

我们选取两个合适的互质常数 b b b 和 h h h（ b < h b<h b<h），假设字符串 C = c 1 c 2 ⋯ c m C=c_1c_2 \cdots c_m C=c1​c2​⋯cm​，那么我们定义哈希函数： H ( C ) = ( c 1 b m − 1 + c 2 b m − 2 + ⋯ + c m b 0 ) m o d h H(C)=(c_1b^{m-1}+c_2b^{m-2}+ \cdots +c_mb^0) \bmod h H(C)=(c1​bm−1+c2​bm−2+⋯+cm​b0)modh。

正常的数字是十进制的，这里 b b b 是基数，相当于把字符串看作是 b b b 进制数。

这一过程是递推计算的。下面讲解省略求模运算，因为可以用自然溢出大法！！！
H ( C , k + 1 ) = H ( C , k ) × b + c k + 1 H(C,k+1)=H(C,k) \times b+c_{k+1} H(C,k+1)=H(C,k)×b+ck+1​
举个栗子：

字符串 C = ACDA C=\texttt{ACDA} C=ACDA，令 1 1 1 表示 A \texttt{A} A， 2 2 2 表示 B \texttt{B} B，以此类推。
H ( C , 1 ) = 1 H ( C , 2 ) = 1 × b + 3 H ( C , 3 ) = 1 × b 2 + 3 × b + 4 H ( C , 4 ) = 1 × b 3 + 3 × b 2 + 4 × b + 1 \begin{aligned} &H(C,1)=1\\ &H(C,2)=1 \times b+3\\ &H(C,3)=1 \times b^2+3 \times b+4\\ &H(C,4)=1 \times b^3+3 \times b^2+4 \times b+1 \end{aligned} ​H(C,1)=1H(C,2)=1×b+3H(C,3)=1×b2+3×b+4H(C,4)=1×b3+3×b2+4×b+1​
判断字符串 C = c 1 c 2 ⋯ c m C=c_1c_2 \cdots c_m C=c1​c2​⋯cm​ 从位置 k + 1 k+1 k+1 开始的长度为 n n n 的子串 C ′ = c k + 1 c k + 2 ⋯ c k + n C'=c_{k+1}c_{k+2} \cdots c_{k+n} C′=ck+1​ck+2​⋯ck+n​ 的哈希值与另一匹配串 S = s 1 s 2 ⋯ s n S=s_1s_2 \cdots s_n S=s1​s2​⋯sn​ 的哈希值是否相等。
H ( C ′ ) = H ( C , k + n ) − H ( C , k ) × b n H(C')=H(C,k+n)-H(C,k) \times b^n H(C′)=H(C,k+n)−H(C,k)×bn

于是只需要预求得 b n b^n bn，就能在 O ( 1 ) O(1) O(1) 时间内得到任意字符串的子串哈希值，从而完成字符串匹配。于是乎，字符串匹配问题的算法时间复杂度就为 O ( n + m ) O(n+m) O(n+m)。

举个栗子：

字符串 C = ACDA C=\texttt{ACDA} C=ACDA， S = CD S=\texttt{CD} S=CD， k = 1 k=1 k=1， n = 2 n=2 n=2。
H ( C ′ ) = H ( C , 1 + 2 ) − H ( C , 1 ) × b 2 = ( 1 × b 2 + 3 × b + 4 ) − ( 1 × b 2 ) = 3 × b + 4 H ( S ) = 3 × b + 4 \begin{aligned} H(C')&=H(C,1+2)-H(C,1) \times b^2\\ &=(1 \times b^2+3 \times b+4)-(1 \times b^2)\\ &=3 \times b+4\\ H(S)&=3 \times b+4 \end{aligned} H(C′)H(S)​=H(C,1+2)−H(C,1)×b2=(1×b2+3×b+4)−(1×b2)=3×b+4=3×b+4​

正确性

出现不同字符串哈希值相等的概率越低越好。

所以有以下两种方法：

• 自然溢出法

  利用 unsigned long long 无符号整数计算哈希值，相当于对哈希值 m o d 2 64 \bmod 2^{64} mod264。

• 双模法

  顾名思义，就是搞一个二元数组存储哈希值， m o d \bmod mod 两个数，两个数都相同哈希值才相同。

实现

Portal.

代码如下：

#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ull;
const int mmax=1505,maxn=10005;
ull base=131,prime=23317,mod=212370440130137957;
int N,a[maxn],ans=1;
char s[mmax];
ull hash[maxn],power[maxn];ull hashh(char s[])
{int len=strlen(s);ull ans=0;for(int i=0;i<len;i++)ans=(ans*base+(ull)s[i])%mod+prime;return ans;
}int main()
{cin>>N;for(int i=1;i<=N;i++)scanf("%s",s),a[i]=hashh(s);sort(a+1,a+N+1);for(int i=1;i<N;i++)if(a[i]!=a[i+1]) ans++;cout<<ans;return 0;
}