文章目錄
-
- 0. 前言
- 1. 字元串哈希
0. 前言
Biu
字元串字首哈希法。預處理出所有字元串字首的哈希,數組存儲,下标從 1 開始存儲。
将字元串看成一個
p
進制的數,例如字首"ABCD"的哈希值:把這個字元串看出
p
進制的數,那麼這個值就是:
h a s h [ 4 ] = ( 1 ∗ p 3 + 2 ∗ p 2 + 3 ∗ p 1 + 4 ∗ p 0 ) % m o d ; hash[4] = (1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p^0 ) \% mod; hash[4]=(1∗p3+2∗p2+3∗p1+4∗p0)%mod;
關于
mod
的經驗值,131 或者 13331,沖突幾率可以忽略不計。
特殊注意:
- 不能将某一個字元映射成數字 0,如果一旦
映射成了數字 0,那麼A
也是數字 0,是以映射成從 1 開始AA
- 這裡的哈希字元串方法是假定不存在沖突的,取上述的模數經驗值即可
這樣的哈希方式,配合字首哈希方式可以求出任意一個子串的哈希值,類似于預處理了字首和,現求子區間和,公式為:
h [ R ] − h [ L ] ∗ p R − ( L − 1 ) h[R] - h[L]*p^{R-(L-1)} h[R]−h[L]∗pR−(L−1)
我們可以采用
unsigned long long
的溢出來代替取模
2^64
。
1. 字元串哈希

模闆:
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5, mod = 13331;
int n, m;
char str[N];
ULL h[N], p[N];
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; str[i]; ++i) {
p[i] = p[i - 1] * mod;
h[i] = h[i - 1] * mod + str[i];
}
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;
}