核心思想
将字符串看成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 ++ )
{
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值
例题
题面
题目链接
题解
#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;
}