CH 1401 兔子与兔子(进阶指南，字符串hash)

算法竞赛进阶指南，68 页， 字符串哈希

本题要点：
1、 求出字符串 str 的所有的前缀字符串的哈希值，那么，str的所有子串的哈希值都可以在 O(1)
的时间内计算出来
2、 计算公式：
子串区间 [L, R]
pre[R] - pre[L - 1] * p^ (R - L + 1)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int p = 131;
const int MaxN = 1000010;
int n;
int query, l1, r1, l2, r2;;
unsigned long long pre[MaxN];	//各个前缀 的哈希值
unsigned long long Left, Right;
unsigned long long p_pow[MaxN];;
char str[MaxN];void init()
{
    n = strlen(str + 1);pre[0] = 0;for(int i = 1; i <= n; ++i){
    pre[i] = pre[i - 1] * p + str[i] - 'a' + 1;	
// printf("pre[%d] = %lld\n", i, pre[i]);}p_pow[0] = 1;for(int i = 1; i < MaxN; ++i){
    p_pow[i] = p_pow[i - 1] * p;}
}int main()
{
    scanf("%s", str + 1);init();scanf("%d", &query);for(int q = 0; q < query; ++q){
    scanf("%d%d%d%d", &l1, &r1, &l2, &r2);	Left = pre[r1] - pre[l1 - 1] * p_pow[r1 - l1 + 1];Right = pre[r2] - pre[l2 - 1] * p_pow[r2 - l2 + 1];
// printf("Left = %lld, Right = %lld\n", Left, Right);if(Left == Right){
    printf("Yes\n");}else{
    printf("No\n");}}return 0;
}/* aabbaabb 3 1 3 5 7 1 3 6 8 1 2 1 2 *//* Yes No Yes */