兔子与兔子

题目 兔子与兔子

image-7c01a70c

思路分析

模板题一模一样

注意别忘了\(p[0]=1\) \(p^0=1\)

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N=1000010,P=131;

char str[N];

ULL h[N],p[N];

int m;

ULL find(int l,int r){

    return h[r]-h[l-1]*p[r-l+1];

}

int main()

{

    cin>>str+1>>m;

    int n=strlen(str+1);

    p[0]=1;

    for(int i=1;i<=n;i++){

        h[i]=h[i-1]*P+str[i];

        p[i]=p[i-1]*P;

    }

    while(m--){

        int l1,r1,l2,r2;

        cin>>l1>>r1>>l2>>r2;

        if(find(l1,r1)==find(l2,r2))

            puts("Yes");

        else

            puts("No");

    }

    return 0;

}

同类题型

视频讲解

⬅️ 字符串哈希 🏠 00-刷题理模型 ➡️ 后缀数组