算法基础班–第二章–P52.字符串哈希模板

算法模板

核心思想：将字符串看成P进制数，P的经验值是131或13331,取这两个值的冲突概率低

小技巧：取模的数用2^64，这样直接用unsigned long long 存储，溢出的结果解释取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; //h[k]存储字符串前k个字母的哈希值，p[k]存储P^k mod 2^64

//初始化
p[0] = 1;
for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P; //P^i
    h[i] = h[i - 1] * P + str[i];//str[i]!=0,数字0，也就是字符串中的字符的ASII不是0，其余所有的字符都可以
}

//计算子串str[l~r]的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

• 求P^i

• p[i] = p[i - 1] * P;

• 公式1：子串str[l~r]的哈希值

• h[r] - h[l - 1] * p[r - l + 1];

• 公式2：预处理前缀的哈希值

• h[i] = h[i - 1] * P + str[i];

本题完整代码

#include <iostream>

using namespace std;
//将字符串看成P进制数，P的经验值是131或13331,取这两个值的冲突概率低
//小技巧：取模的数用2^64，这样直接用unsigned long long 存储，溢出的结果解释取模的结果
typedef unsigned long long ULL;

const int N = 100010, P = 131;//P进制
int n, m;
char str[N];
ULL h[N], p[N]; //h[k]存储字符串前k个字母的哈希值，p[k]存储P^k mod 2^64

//计算子串str[l~r]的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    scanf("%d%d%s", &n, &m, str + 1); //下标从1开始
    //初始化
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P; //P^i
        h[i] = h[i - 1] * P + str[i];//str[i]!=0,数字0，也就是字符串中的字符的ASII不是0，其余所有的字符都可以
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}