Hash表也叫散列表
我们可以利用Hash表来比较字符串是否相等
如果一个个字符进行比较，时间复杂度就为O(n)
所以，把每个字符或字符串映射成一个整数来进行比较这些整数是否相等，这样时间复杂度就为O(1)。
这个映射函数叫做hash函数，存放记录的数组叫做hash表。
例如：a我们可以表示为1,b就为2....abc就是123.比较abc和abc就是看123是否等于123....26个字符就是：a-z（1-26）.

为了尽可能不重复，我们把各字符映射成的整数然后存在hash表里的数都弄成131或13331进制的数（以下以131为主）
hash(a)=1
hash(ab)=1131+2=133//乘131表示移位，让一位来存上2
hash(abc)=1131^2+2*131+3=17426
abc如果要跟另外一个字符比较，只要比较那个字符的hash值是否为17426即可。
在unsigned long long中溢出就表示模了2的64次方，所以hash表的类型应该用unsigned long long

如何算出h[r]到h[l]之间的字符串的值呢？
如图：图片说明
（画的丑不要喷QAQ）
红笔表示把h[l-1]这些跟移到另外那里。
所以在弄个p[]数组，存下131的各个次方。
再结合图就可得出：h[l到r]=h[r]-h[l-1]*p[r-l+1]

看题：
题目描述
很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
输入描述:
第一行一个 DNA 字符串 S。
接下来一个数字 m，表示 m 次询问。
接下来 m 行，每行四个数字 l1, r1, l2, r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
其中 1 \leq length(S)1≤length(S),m \leq 1000000m≤1000000
输出描述:
对于每次询问，输出一行表示结果。如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）

实际上就是比较两个区间是否相同

代码：

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

using namespace std;

typedef unsigned long long ULL;

const int N = 1000010, base = 131;

char s[N];
ULL p[N], h[N];//p进制数和hash

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;//p的0次方为1
    for (int i = 1; i <= n; i++) {
        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;
}