题解|《算法竞赛进阶指南》 兔子与兔子

题目描述
很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入描述:
第一行一个 DNA 字符串 S。
接下来一个数字 m，表示 m 次询问。
接下来 m 行，每行四个数字 l1, r1, l2, r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
其中 1≤length(S),m≤1000000。

输出描述:
对于每次询问，输出一行表示结果。如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）

思路：
这题是一道字符串hash的模板题，所以也没什么好讲的。

稍微的说说：
字符串哈希,最著名的就是BKDRHash,也就是将字符串变成数值,并且最后变成的数值是一个P进制的数,一般来说P最好为素数.这个题目是求一个区间的字符串所以需要前缀和。

完整C++版AC代码：

#include <iostream>
#include <string.h>

using namespace std;

typedef unsigned long long ULL; //自动取模

const int N = 1000010, base = 131;//Hash值131最好,当然还有1331

char s[N];
ULL p[N], h[N];

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

int main() {

    scanf("%s", s + 1);
    int n = strlen(s + 1);
    p[0] = 1;//131的0次方是1
    for (int i = 1; i <= n; i++) {
        // 将小写字母映射到[1, 26]
        h[i] = h[i - 1] * base + s[i] - 'a' + 1;
        p[i] = p[i - 1] * base;
    }
    int m;
    scanf("%d", &m);
    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;
}