bryce 1010 테마 - 문자열 HASH

bryce 1010 테마 - 문자열 HASH
문자열 Hash 함 수 는 임의의 길이 의 문자열 을 부정 정수 로 표시 하고 충돌 할 확률 이 거의 0 입 니 다.고정 값 P 를 가 져 와 문자열 을 P 진수 로 보고 0 이상 의 수 치 를 할당 하여 모든 문 자 를 대표 합 니 다.이 문자열 의 Hash 값 으로 고정 값 M 을 가 져 옵 니 다.일반적으로 우 리 는 P = 131 또는 P = 13331 을 취하 는데 이때 Hash 값 이 충돌 할 확률 이 매우 낮다.Hash 값 이 같 으 면 원 문자열 이 같다 고 볼 수 있 습 니 다.보통 우 리 는 M = 2 ^ 64, 즉 unsigned long 형식 으로 이 Hash 값 을 저장 합 니 다.
O (N) 의 시간 을 통 해 문자열 의 모든 접두사 Hash 값 을 미리 처리 하고 O (1) 의 시간 내 에 임의의 하위 문자열 의 Hash 값 을 조회 할 수 있 습 니 다.
1. 기본 해시 템 플 릿
CH 1401 토끼 와 토끼 가 한 문자열 을 맞 추고 두 단락 의 문자열 을 임의로 맞 추 면 두 개의 문자열 이 같 습 니까?

#include
#define MAX 1000010
using namespace std;
char a[MAX];
unsigned long long f[MAX],zifu[MAX];
int n,la,ra,lb,rb,lena;
long long same(int l,int r){
	return zifu[r]-zifu[l-1]*f[r-l+1];
}
int main(){
	scanf("%s",a+1);
	lena=strlen(a+1);
	f[0]=1;zifu[0]=0;
	for(int i=1;i<=lena;i++){
		f[i]=f[i-1]*131;
		zifu[i]=zifu[i-1]*131+(a[i]-'a'+1);
	}
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&la,&ra,&lb,&rb);
		if(same(la,ra)==same(lb,rb)){
		cout<<"Yes"<<endl;	
		}
		else cout<<"No"<<endl;
	}
	
	
	return 0;
}