字符串哈希

题目

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m，表示字符串长度和询问次数。第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes

分析

这个题看的时候觉得是不是可以用substr函数来做，后来想想觉得没毛病，但是又觉得如果可以的话，那么KMP的字符串匹配不是也可以用substr来代替，那这两个算法就没有用了，后来用substr交了试试，被一个很大很多的数据TLE了，，问了大佬，substr的时间复杂度是O(n)的，所以，字符串哈希还是很值得学习的，，，，

首先要把字符串的每一个前缀都想象成为一个p进制的数，h[1]就是前一个字符的哈希，h[2]就是前两个字符的哈希，h[3]就是前三个字符的哈希。。这样的话最后就可能会非常大，所以要模上一个数Q，p可以选131，也可以选13331，Q一般选成2的64次方，这样冲突比较小，因为字符串哈希是没有办法解决冲突的。。因为要模除于一个2的64次方，所以可以直接用unsigned long long，因为他溢出就相当于取模了。

这样求出的字符串前缀哈希就可以求出任何一个字串(L,R)的哈希值,公式就是h[R]-+1h[L-1]*p^(R-L+1)，如果两个字串的哈希值一样的话就认为他们相等

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int N=100009;
const int p=131;
ull pi[N],h[N];

int main()
{
    int n,m;
    string s;
    cin>>n>>m>>s;
    pi[0]=1;
    for(int i=1;i<=n;i++)      pi[i]=pi[i-1]*p;  //预处理一个p的前n项的乘积
    for(int i=1;i<=n;i++)      h[i]=h[i-1]*p+s[i-1];  //处理字符串的每一位
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(h[r1]-h[l1-1]*pi[r1-l1+1]==h[r2]-h[l2-1]*pi[r2-l2+1]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}