字符串hash

╰半橙微兮° 2021-06-22 15:36 385阅读 0赞

## 字符串哈希 ##

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。
    
    字符串中只包含大小写英文字母和数字。
    
    输入格式
    第一行包含整数n和m，表示字符串长度和询问次数。
    
    第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
    
    接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。
    
    注意，字符串的位置从1开始编号。
    
    输出格式
    对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
    
    每个结果占一行。
    
    数据范围
    1≤n,m≤105

#include <iostream>
    using namespace std;
    typedef unsigned long long ull;
    const int N=1e5+10,p=131;//p最好为131和13331这样冲突可能少一些 
    int n,m;
    char str[N];
    ull h[N],b[N];//取模的q最好取2的64次方，因此定义为unsigned long long类型
     //溢出时相当于是自动取模 ，b数组用来存储p的多少次方 
    //注意a和b都必须从1开始

void in_hash(){ 
    	b[0]=1;
    	for(int i=1;i<=n;i++){ 
    		b[i]=b[i-1]*p;
    		h[i]=h[i-1]*p+str[i];//前缀法求哈希值方便一步计算一段范围内的hash值 
    		//把字符串当作p进制的数 
    	}
    }

ull get_hash(int l,int r){ 
    	return h[r]-h[l-1]*b[r-l+1];//求l，到r的hash值。将l-1位向高位平移r-l+1位于r相对 
    }

int main()
    { 
    	cin>>n>>m;
    	cin>>str+1;
    	in_hash();
       while(m--){ 
       	int l1,r1,l2,r2;
       	cin>>l1>>r1>>l2>>r2;
       	 if(get_hash(l1,r1)==get_hash(l2,r2)){ 
       	 	cout<<"Yes"<<endl; 
    		}
    		else{ 
    			cout<<"No"<<endl;
    		}
       }
    	
    	return 0;
     }