哈希处理字符串（模板）

841. 字符串哈希 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
#define int  long long
#define endl '\n'
const int N=1e5+10;
int p=131;//13331
int  P[N],h[N];//P存的是p的k次方，h存字符串前k个数（换化成ascll码）

int  find(int l,int r)
{
    return h[r]-h[l-1]*P[r-l+1];//返回l~r之间的值 
}



signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n,m;
    cin>>n>>m;
    string s;
    P[0]=1;
    h[0]=0;//初始化 
    cin>>s;
    for(int i=0;i<n;i++)
    {
        P[i+1]=P[i]*p;//存p的i次方 
        h[i+1]=h[i]*p+s[i];//存哈希值 
        
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(find(l1,r1)==find(l2,r2))
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
      
      
    
    
    
}