【散列表】字符串哈希快速判重-LMLPHP

导读 ^ _ ^

字符串哈希能够帮我快速判断两个字符子串是否相同。
非常的好用！

字符串哈希

何为字符串哈希

字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。并且，用h[N]记录字符串前N个字符的Has值，类似于前缀和。

映射方式

映射方式：
对形如
X1 X2 X3 ... Xn−1 Xn 的字符串，采用字符 ASCII 码乘上 P 次方来计算哈希值。
映射公式：(X1×Pn−1 + X2×Pn−2 + ... + Xn−1×P1 + Xn×P0) mod Q
【散列表】字符串哈希快速判重-LMLPHP

哈希前缀和应用

问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就类似于构建一维前缀和，求一个字符串的子串哈希值就相当于一维前缀和应用:
构建： h[i]=h[i−1]×P+s[i] i∈[1,n] h为前缀和数组，s[i−1]为字符串数组此位置字符对应的ASCII码。
应用：查询l,r之间部分字符串的hash=h[r]−h[l−1]×Pr^(−l+1)
【散列表】字符串哈希快速判重-LMLPHP

解决哈希冲突与技巧

任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
冲突问题：通过巧妙设置P(131或13331) ,Q(264这个取模动作在代码中没有出现过，这是因为采用了unsinged long long，它本身就是2^64,如果超过了这个数字，就直接自动溢出，起到了取模的作用。

代码实现

#include<iostream>
#include<cstring>
#include<string>

using namespace std;
typedef unsigned long long ULL;//利用 unsigned long long 自然溢出，相当于自动对2^64取模。

const int N = 100010;
const int P = 131; //经验,P进制

int n,m;
char str[N];
ULL h[N],p[N];//h表示某一个前缀的HASH值,h[R]表示的是前R个字母的HASH值,p代表p进制，目前是131进制


ULL get(int l, int r) {
    return h[r] - h[l-1]*p[r-l+1];
}

int main( ) {
    cin >> n >> m >> str + 1;
    p[0] = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = p[i-1]*P; //预处理乘方
        h[i] = h[i-1]*P + str[i]; //计算前i个字符的字符串前缀hash值
    }

    while(m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

阿新的杂记

【散列表】字符串哈希快速判重