字符串前缀哈希值

这是一个完爆kmp算法的一个算法，kmp除了可以在求循环节上比哈希有用，其他方面的用处都被哈希完爆
所以没事就写哈希就可以了，kmp还难写，何必呢？

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;   //P取了一个ascii码的范围值
//N就是用来作下标的，字符串的长度不超过1e5，所以N=100010;
ULL h[N],p[N];//P^10次方到最后肯定会爆ULLint的，但是爆了之后他就相当于mod了一个2^64
//重新开始记，放心好了，99%都不会冲突的
int query(int l,int r)
{
   return h[r]-h[l-1]*p[r-l+1];//很好理解啊，就是P进制数里面单独把[l,r]这一段数拿出来而已
//需要做一个简单的计算，这里就用上我们之前的字符串前缀哈希值处理了
//比如说一串数654321,我们要取[2，5],那就是要用从左到右5位的数值减去从左到右(2-1)位的数值*P^[5-(2-1)]
//原式=65432-6*10^4
//    =65432-60000
//    =5432
//2345嘛四位

}
int main()
{
    int n,m;
    char x[N];
    cin>>n>>m>>x+1;
    //接下来我们来做字符串前缀哈希值的预处理，方便等下m--循环里面的查表操作
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+x[i];//这里直接用了x第i位的ascii码，直接加了一个整数上去啊
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1)==query(l2,r2))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}