138. 兔子与兔子【字符串哈希】

很基础的字符串哈希

#include<bits/stdc++.h> using namespace std; typedef unsigned long long int ull; const int N=1e6+10; const int M=233; ull base[N],h[N],n; string s; void init() {base[0]=1;for(int i=1;i<N;i++) base[i]=base[i-1]*M; } ull get(int l,int r)//获取字符串[l,r]的哈希值 {return h[r]-h[l-1]*base[r-l+1]; } int main(void) {cin>>s;s="0"+s;init();for(int i=1;i<s.size();i++) h[i]=h[i-1]*M+s[i]-'a';cin>>n;while(n--){int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;ull sum1=get(l1,r1);ull sum2=get(l2,r2);if(sum1==sum2) puts("Yes");else puts("No");}return 0; }

总结

以上是生活随笔为你收集整理的138. 兔子与兔子【字符串哈希】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。