字符串哈希-最易懂的证明

题目

给定一个长度为 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⁵
输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

题目解析：

给出一个字符串，例如 s = "adcdabcde"
给出[l1, r1]，[l2, r2]
问字符串的子串 s[l1, r1] s[l2, r2] 是否相同

解题思路：

1. 思路一：暴力，超时。

2. 思路二：字符串哈希

将字符串转换成一个P进制的数字，例如 131 进制的数字。这个值看做字符串的哈希值h。

相同的字符对应的P进制数字一定相同，即哈希值相同。

因为进制取得131，认为哈希值相同的字符是相等的。

因此，只要能快速求出s[l1, r1] 和 s[l2,r2]对应的字符串的哈希值h[s[l1, r1]] h[s[l2, r2]]，并判断是否相等。就能得出l1, r1 l2,r2对应的字符串是否相同

具体算法

如何快速求出s[l, r]的哈希值h[s[l,r ]]是关键。这里可以使用前缀和思想。

字符串s的下标从1开始，字符串长度为n。P 取131。字符串s[1, t]对应的哈希值记为h[t]。

1. 分别求出 h[1], h[2], h[3],h[n]

2. 此时

 h[s[l, r]] = h[r] - h[s[l - 1]] * pow(131, r - l + 1)

为什么？举个例子

例如s = "abcabcd", 各个位置对应的数字为：

s = "97 98 99 97 98 99 100"

h[1] = 97
h[2] = h[1] * P + h['b'] = 97 * 131 + 98 = 12,805
h[3] = h[2] * P + h['c'] = 12805*131 + 99 = 1,677,554
h[4] = h[3] * P + h['a'] = 1,677,554 * 131 + 97 = 219,759,671‬
h[5] = h[4] * P + h['b'] = 219,759,671‬ * 131 + 98 =28,788,516,999‬
h[6] = h[5] * P + h['c'] = 28,788,516,999‬ * 131 + 99 = 3,771,295,726,968
h[7] = h[6] * P + h['d'] = 3,771,295,726,968 * 131 + 100 = 494,039,740,232,908‬

求 h[s[2, 3]]

1. h[3] = h['abc'] = h['a'] * pow(P, 2) + h['b'] * pow(P, 1) + h['c'] = 1,677,554

2. h[1] = h['a'] = 97

3. h[s[2, 3]] = h['bc'] = h['b'] * pow(P, 1) + h['c']

4. 所以：h[s[2, 3]]= h[3] - h[1] * pow(P, 2) = 12,937‬

5. 也就是：h[s[l, r]] = h[r] - h[l - 1] * pow(P, r - l + 1)

再举个例子

以s为数字字符串，各个位置的值等于数字本身，P等于10，说明h[s[l, r]] = h[r] - h[s[l - 1]] * pow(P, r - l + 1)

s = '4564'

h[1] = 4
h[2] = 45
h[3] = 456
h[4] = 4565
h[s[2,3]] = 456 - 4 * 100 = h[3] - h[1] * pow(10, 2)

代码：

C++代码

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
}
int main(){
    int n,m;
    cin>>n>>m;
    string x;
    cin>>x;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P;            
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}

Python代码

import sys
n, m = map(int, sys.stdin.readline().split())
P = 131
s = input()
Q = 1 << 64
h = [0] * (len(s) +  10)
p = [0] * (len(s) +  10)
p[0] = 1
s = " " + s
# 根据公式求
def get(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % Q

# 初始化
for i in range(1, len(s)):
    h[i] = (h[i - 1] * P + ord(s[i])) % Q
    p[i] = p[i - 1] * P % Q

while m:
    m -= 1
    l1, r1, l2, r2 = map(int, input().split())
    if get(l1, r1) == get(l2, r2):
        print("Yes")
    else:
        print("No")