字符串哈希

⬅ 返回

1、本质

全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。

2、例题

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

3、代码

#include <iostream>
 
using namespace std;
 
const int N = 1e5 + 10;
char str[N];
int P = 131; //令p取131 或 13331 在%99的情况下不会起冲突 记住就好
int p[N], h[N];
//把字符串映射为p进制的整数
 
int main()
{
    int n, m;
    cin >> n >> m;
    cin >> str + 1;
 
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + str[i]-'a'+1;//求前i个字符的哈希值
        p[i] = P * p[i - 1];//p[i]=p^i;
    }
 
    while (m--)
    {
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;
        if (h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}