acwing841. 字符串哈希

给定一个长度为 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

分析

举例 ：对于一个字符串"ABCDEF"我们可以用h[N]来表示从0-N的字符串的哈希值，如h[0]表示“A",h[1]表示“AB”...然后我们用哈希映射出每个字符串的值，映射公式：h[i]=s[0] * p⁰ + s[1] * p ¹ +...+ s[i-1] * p ^(i-1) % 2 ⁶⁴.对于模2^64，我们可以利用unsigned long long 来存储，因为如产生溢出会自动取模。最后若要取l,r之间的字符穿是否相等，我们可以设计qurry函数，返回l，r之间的哈希值，而方法可用h[r]-h[l-1]*p[r-l+1]来求得。

代码

思路

将字符串的每个字母用数值来表示，每个值在不产生冲突情况下对应的字符串相同。h[N]表示字符串每个字母对应的哈希值，P=131是经验值，p[N]用来表示p的次方，unsinged long long溢出自动取模。这种方法产生冲突的概率很小，但是如果产生冲突就会出现错误。

#include<iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL; 
const int N=1e5+10,P=131;
ULL h[N],p[N];
char str[N];

ULL get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

int main(){
    int n,m;
    cin>>n>>m;
    scanf("%s",str+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
    }
    int l1,l2,r1,r2;
    while(m--){
        cin>>l1>>l2>>r1>>r2;
        if(get(l1,l2)==get(r1,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}