CH1401 兔子与兔子

这是一道字符串哈希模板题
为了避免被卡，我使用了双模哈希。。。自然溢出取模。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#define ULL unsigned long long
using namespace std;
template<class T>
inline void read(T& p) {
    char c;
    p=0;
    bool f=0;
    for(c=getchar(); c<'0'||c>'9'; c=getchar())if(c=='-')f=true;
    for(; c>='0'&&c<='9'; c=getchar()) p=(p<<3)+(p<<1)+c-'0';
    if(f)p=-p;
}
template<class T,class... Args>
inline void read(T& x,Args&... args) {
    read(x);
    read(args...);
}
template<class T>
inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
template<class T,class... Args>
inline void write(T x,Args... args) {
    write(x);
    putchar(' ');
    write(args...);
}
template<class... Args>
inline void writeln(Args... args) {
    write(args...);
    putchar('\n');
}
const int N=1000010;
ULL f1[N],f2[N],p1[N],p2[N];
char s[N];
int main() {
    scanf("%s",s+1);
    int n=strlen(s+1),q;
    read(q);
    p1[0]=p2[0]=1;
    for(register int i=1;i<=n;i++){
        f1[i]=f1[i-1]*131+(s[i]-'a'+1);
        f2[i]=f2[i-1]*13331+(s[i]-'a'+1);
        p1[i]=p1[i-1]*131;
        p2[i]=p2[i-1]*13331;
    }
    for(register int i=1,l1,l2,r1,r2;i<=q;i++){
        read(l1,r1,l2,r2);
        if(f1[r1]-f1[l1-1]*p1[r1-l1+1]==f1[r2]-f1[l2-1]*p1[r2-l2+1]&&f2[r1]-f2[l1-1]*p2[r1-l1+1]==f2[r2]-f2[l2-1]*p2[r2-l2+1]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
    return 0;
}

CH1401 兔子与兔子

原文：https://www.cnblogs.com/STOGMH/p/11811428.html