字符串哈希

字符串哈希

Solost

2023 年 04 月 13 日

206 次浏览

暂无评论

504字数

ACM笔记

## 核心思想

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

## 模板

```cpp
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 ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

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

## 求一个数的hash值

求一个数的hash值其实就是把这个数字转换成p进制，转换后的数就是hash值

## 例题

### 题面

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F13%2Fimage.png)

### 题目链接

[链接](https://www.acwing.com/problem/content/843/)

### 题解

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007, P = 131;
const int N = 2e5 + 10;

ull h[N], p[N];

ull get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
    /*
	区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
	乘上P的二次方把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。
	相当于求abc的哈希值，把abc往后顶r - l + 1位，然后相减得到的就是hash值
    */
}

void solve()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = ' ' + s;
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    while(m--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1, r1) == get(l2, r2)){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 13 日