欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

[算法] 字符串散列 - 完整代码

最编程 2024-07-15 17:04:10
...
# include <iostream>
# include <cstring>
# include <cmath>

using namespace std;
const int p = 131;
const int N =1e5+5;
unsigned long long h[N],pp[N];



unsigned long long query(int l,int r){
     return h[r] - h[l-1]*pp[r-l+1];
 }

int main(){
    int n,m;
    cin>>n>>m;
    string str;
    cin>>str;
    int i;
    h[0] = 0;
    pp[0] = 1;
    for(i=0; i<n;i++){
        pp[i+1] = pp[i] * p;
        h[i+1] = h[i] * p + str[i];
        //cout<<h[i+1]<<endl;
    }
    
    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;
        }
        
    }
    
}

推荐阅读