[字元串哈希+模闆]字元串哈希

文章目錄

• • 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，如果一旦

  A

  映射成了數字 0，那麼

  AA

  也是數字 0，是以映射成從 1 開始
• 這裡的哈希字元串方法是假定不存在沖突的，取上述的模數經驗值即可

這樣的哈希方式，配合字首哈希方式可以求出任意一個子串的哈希值，類似于預處理了字首和，現求子區間和，公式為：

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;
}