top1编程
← 返回题目
题解

【基础】DNA序列判重

1 条题解

  • 0
    @ 2026-7-29 0:18:14
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef unsigned long long ULL; 
    const int N=1000100,base=131;
    char str[N];
    ULL h[N],p[N];
    
    //求l~r之间的hash值 
    ULL get(int l,int r){
    	return h[r] - h[l-1] * p[r-l+1];
    }
    
    int main() {
    	scanf("%s",str+1);
    	int n = strlen(str+1);
    	
    	p[0] = 1;
    	for(int i = 1;i <= n;i++){
    		//将小写字母映射为1~26
    		h[i] = h[i-1] * 131 + (str[i] - 'a' + 1);
    		p[i] = p[i-1] * base;
    	}
    	
    	int l1,r1,l2,r2;
    	cin>>n;
    	for(int i = 1;i <= n;i++){
    		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
    		if(get(l1,r1)==get(l2,r2)){
    			printf("%s&#92;n","Yes");
    		}else{
    			printf("%s&#92;n","No");
    		}
    	}
    }
    
    • 1