AcWing 841 字元串哈希 題解 （字元串哈希 模闆）（哈希表 Hash）

字元串哈希的原理：将每段字元串化為P進制的數，賦予唯一的‘位址 ’，通過位址比較字元串，時間複雜度為O(1),如果挨個字元進行比較，時間複雜度為O(字元串長度)

#include<iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;//P經驗值131、1331

int h[N], p[N];//h數組儲存以末尾字元為标志的每段字元串的特殊‘位址 ’，p儲存P的幂 
char str[N];
int n, m;

ULL get(int r, int l){
	return h[r] - h[l - 1] * p[r - l + 1];//求第l到第r位之間字元串對應‘位址 ’的公式(推導過程問本人） 
} 

int main()
{
	scanf("%d%d%s", &n, &m, str + 1);//後期處理字元串都是從1開始，是以讀入字元串的下标也從1開始
	p[0] = 1;//防止p數組都是0 
	for(int i = 1; i <= n; i ++ ){//将字元串轉換為P進制 
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + str[i];//因為h[i]的值是由h[i-1]決定的，是以h[i]代表從第一個字元開始到第i個字元結束的字元串的‘位址 ’ 
	} 
	while(m -- ){
		int r1, r2, l1, l2;
		cin>>l1>>r1>>l2>>r2;
		if(get(r1, l1) == get(r2, l2)){//如果兩段字元串的‘位址 ’相同，代表兩段字元串相同 
			cout<<"Yes"<<endl;
		}
		else if(get(r1, r1) != get(r2, l2)){//如‘位址 ’不同，則字元串不同 
			cout<<"No"<<endl;
		} 
	} 
	return 0; 
}