字符串前缀哈希
当遇到如比较两个区间内的字符是否相同时 可以用这种方法 十分快速

此方法精髓在于用数来表示哈希值 便于理解与记忆 用P=10即十进制来理解
如1234
h[0]=0 注意从h[1]开始存 不然A为0 算下去AA也为0 所以从1开始
h[1]=h[0]P+str[1]=010+1=1
h[2]=h[1]P+str[2]=110+2=12
h[3]=h[2]P+str[3]=1210+3=123
h[4]=h[3]P+str[4]=12310+4=1234

若求一个区间 如L=3 R=4 即34
则是 1234-12*10^2
即 h[4]-h[2]*P^2
即L到R之间的哈希值为 h(R)-h(L-1)*P^(R-L+1) 题里这个P的次方用数组p[]存 需要初始化一下
P一般取131

防止长度过长本需mod Q
unsigned long long来存储h 它可以溢出 溢出时就相当于模了一个2的64次方

[字符串前缀哈希法] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N=100010,P=131;

int n,m;
char str[N];
ULL h[N],p[N];//h[]存某个前缀的哈希值 p[]存是多少次方

ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1]; //本来h[r]的高位更大
}

int main()
{
    cin>>n>>m>>str+1;
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P; //这一步一定要理解
        h[i]=h[i-1]*P+str[i];
    }

    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;

        if(get(l1,r1)==get(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    }
    return 0;
}


一般比较字符串就用这个方法