当前位置:首页 > Windows程序 > 正文

AcWing 841. 字符串哈希

标签:return   har   include   ret   div   col   nbsp   unsigned   long   

//快速判断两次字符串是不是相等 
#include<bits/stdc  .h>
using namespace std ;
typedef unsigned long long ULL;
const int N=100010,P=131;//经验值 13331  这两个出错情况最少 
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];//返回某一段的哈希值 
}
int main() {
    cin>>n>>m>>str 1;
    p[0]=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)) puts("Yes");// 如果哈希值相等 
        else puts("No");
    }
    return 0;
}

 

 

AcWing 841. 字符串哈希

标签:return   har   include   ret   div   col   nbsp   unsigned   long   

温馨提示: 本文由杰米博客推荐,转载请保留链接: https://www.jmwww.net/file/14421.html