AcWing 841. 字符串哈希

字符串哈希 - 哈希表

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 10, P = 131;

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];
    //返回l到r这个区间内的哈希值 看是否一样
}

int main(){
	scanf("%d%d%s", &n, &m, str + 1);
	p[0] = 1;
	for(int i = 1; i <= n; i++){
		p[i] = p[i - 1] * P;
		//预处理P多少的次方
		h[i] = h[i - 1] * P + str[i];
		//预处理哈希值
	}
	while(m--){
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if(get(l1, r1) == get(l2, r2)) puts("Yes");
		else puts("No");
	}
	return 0;
	
}

![[Pasted image 20221224123939.png]]
![[Pasted image 20221224132630.png]]
![[Pasted image 20221224132359.png]]
![[Pasted image 20221224134156.png]]
![[Pasted image 20221224134402.png]]

//不能映射成0 A = 0 AA = 0
//Rp足够好，不存在冲突 即 P = 131 或 13331 Q = 2 ^ 64 99%是不会发生冲突的

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];
//因为要 % 2的64次方所以可以直接用unsigned long long 直接溢出

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

int main(){
    scanf("%d%d%s", &n, &m, str + 1);
    
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];//str[i]只要保证不是0就可以，是多少都可以
    }
    
    while(m--){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}