字符串哈希

哈希函数是指将任何一种类型的变量$x$映射到$hash(x)$里，其中$hash(x)$是比较小的数值。一般来说，我们希望这种函数是一对一的，但偶尔会出现哈希碰撞的情况，即一对多的情况。这种情况是不可取的。

$$hash(i) = \sum_{i=1}^l p^{l-i}\times s[i]\mod Q$$

很多情况下，我们都将字符串的起始下标设为1.

在这里，$hash(i)$表示从1到下标$i$这个字符串的哈希值。所以我们要先确定前缀字符串，比如给定：

$$s ="ABCDEF"$$

那么$hash(0)=hash(“A”)，hash(1)=hash(“AB”)…$

在计算的时候，我们把字符串当作$p$进制数，并按照ASCII码赋值，其hash函数就是将$p$进制数转换成10进制数。因此：

$hash(“ABCD”)=hash(979899100{base})=hash((97p^3+98p^2+99*p^1+100){10})$

至于如何取$p$，经验来讲，对于字符串哈希，可以选取$p = 131\ or\ 13331$。

而模数$Q$，可以取$2^{64}$。这两个取数一般情况下不会出现哈希冲突。

由于模数可以取$2^{64}$，那么可以使用unsigned long long类型，这个类型有自然溢出，故不需要我们人为取模。

求出hash之后，我们比如有$0\sim n-1$的字符串，其中要计算$hash(l\sim r)$。我们应该这样做：

首先，将$0\sim l-1$的hash值左移（相当于十进制数中12，乘以10的2次方，就成了1200），直到与$0\sim r$的位数相同。然后两式子相减，就可以了。不难知道，要左移$r-l+1$位。

由于我们把字符串看成$p$进制数，所以这一个过程可以看作：

$$hash(l\sim r) = hash(r)-hash(l-1) * p^{r-l+1}$$

所以如果某两段子串是相同的，那么有$hash(l_1 \sim r_1)=hash(l_2 \sim r_2)$，这样比较字符串就方便很多了！

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
typedef unsigned long long ull;
typedef long long ll;
ull q = 133331;
//指数数组，哈希数组
ull p[MAXN], hashh[MAXN];
int n, t;
string s;

ull getHash(int l, int r) {
    return hashh[r] - hashh[l - 1] * p[r - l + 1];
}

int main(){
    cin >> n >> t >> s;
  	//将字符串左移，这样下标从1开始了
    s = " " + s;
    p[0] = 1;
  	//从1开始，计算字符串的哈希值，这里就跟进制转换基本一样的
    for(int i = 1; i <= n; i ++ ){
        p[i] = p[i - 1] * q;
        hashh[i] = hashh[i - 1] * q + s[i];
    }
  	//t组查询
    while (t--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        printf("%s", getHash(l1, r1) == getHash(l2, r2) ? "Yes\n" : "No\n");
    }
}

字符串哈希

http://blog.inverseda.top/2021/03/20/算法笔记/字符串哈希/

Author

InverseDa

Posted on

2021-03-20

Updated on

2023-03-30

Licensed under

#字符串哈希函数