AcWing - 字元串哈希(字元串查詢)

題目連結:https://www.acwing.com/problem/content/description/843/

時/空限制：1s / 64MB

題目描述

給定一個長度為n的字元串，再給定m個詢問，每個詢問包含四個整數l1,r1,l2,r2，請你判斷[l1,r1]和[l2,r2]這兩個區間所包含的字元串子串是否完全相同。

字元串中隻包含大小寫英文字母和數字。

輸入格式

第一行包含整數n和m，表示字元串長度和詢問次數。

第二行包含一個長度為n的字元串，字元串中隻包含大小寫英文字母和數字。

接下來m行，每行包含四個整數l1,r1,l2,r2，表示一次詢問所涉及的兩個區間。

注意，字元串的位置從1開始編号。

輸出格式

對于每個詢問輸出一個結果，如果兩個字元串子串完全相同則輸出“Yes”，否則輸出“No”。

每個結果占一行。

資料範圍

1≤n,m≤10^5

輸入樣例

8 3

aabbaabb

1 3 5 7

1 3 6 8

1 2 1 2

輸出樣例

Yes

No

Yes

解題思路

題意:判斷[l1,r1]和[l2,r2]這兩個區間所包含的字元串子串是否完全相同。

思路:将字元串看成P進制數(判斷兩個整數是否相等好判斷)，P的經驗值是131或13331，取這兩個值的沖突機率低。

根據定義分别求出hash[i]:

• hash[1]=s1
• hash[2]=s1∗p+s2
• hash[3]=s1∗p^2+s2∗p+s3
• hash[4]=s1∗p^3+s2∗p^2+s3∗p+s4
• hash[5]=s1∗p^4+s2∗p^3+s3∗p^2+s4∗p+s5

現在我們想求s3s4的hash值，不難得出為s3∗p+s4,并且從上面觀察，如果看hash[4]−hash[2]并将結果中帶有s1,s2系數的項全部消掉，就是所求。但是由于p的階數，不能直接消掉，是以問題就轉化成，将hash[2]乘一個關于p的系數，在做差的時候将多餘項消除，進而得到結果。

• hash=hash[r]−hash[l−1]∗p^(r−l+1)

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int P = 131;
const int MAXN = 1e5 + 5;
typedef unsigned long long ULL;
ULL h[MAXN], p[MAXN]; // h[k]存儲字元串前k個字母的哈希值, p[k]存儲 P^k mod 2^64
char str[MAXN];
// 初始化
void init(int n) {
    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];
}
int main() {
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);
    init(n);
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) != get(l2, r2))
            printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}