为啥RE了TT
查看原帖
为啥RE了TT
1055881
DangX楼主2024/7/21 12:10
#include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  typedef unsigned long long ULL;
  #include <string>
  // 解题思路: 
  
  const int N=1e5+5; // 字符串数量上界
  const int M=1.5e3+10; // 单个字符串最大长度
  const int P=131; // 131,13331不容易哈希碰撞
  
  // h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值
  ULL p[N],h[N];
  char s[M]; // 存储字符串
  ll n;
  // 计算字符串s的哈希值
  void init() {
   	// p^0=1,空串哈希值为0
   	p[0]=1,h[0]=0;
	int len=strlen(s);
   	for(int i=1;i<=len;i++) {
   		p[i]=p[i-1]*P;	
   		h[i]=h[i-1]*P+s[i-1]; // 前缀和计算公式
   	}
   }
  ULL Hash(char s[]) {
  	h[0]=0; // 空串哈希值为0
  	int len=strlen(s); // 计算长度
  	for(int i=1;i<=len;i++) {
  		h[i]=h[i-1]*P+s[i-1];	
  	}
  	return h[len]; // 返回此串的哈希值
  }
 
 // 预处理hash函数的前缀和,时间复杂度O(n)
 ULL get(int l,int r) {
  	return h[r]-h[l-1]*p[r-l+1]; // 区间和计算字串的hash值
}
int main(){
	cin>>s;
	init();
	Hash(s);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(get(a,b)==get(c,d))
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	
	return 0;
}
2024/7/21 12:10
加载中...