Hash table, string hash (special KMP)

Hash table storage structure （ Handling conflicts ）

Zipper method

Linked forward star stores the structure of adjacency list
The hash table length is taken as a prime number , And leave 2 As far as possible , The minimum prime number greater than the search range of the topic

840. Simulation hash table

Maintain a collection , The following operations are supported ：

I x, Insert a number x;
Q x, Ask the number x Whether there has been... In the collection ;
Now it's time to N operations , For each query operation, the corresponding result is output .

Input format
The first line contains integers N, Represents the number of operations .

Next N That's ok , Each line contains an operation instruction , The operation instruction is I x,Q x One of the .

Output format
For each inquiry instruction Q x, Output a query result , If x In the collection , The output Yes, Otherwise output No.

Each result takes up one line .

Data range
$1\le N\le 10^5$
$-10^9\le x\le 10^9$
sample input ：
5
I 1
I 2
I 3
Q 2
Q 5
sample output ：
Yes
No

#include<iostream>
using namespace std;
const int N=100003;
struct node{
    
	int to;
	int next;
}e[N];
int cnt;
int h[N];
void insert(int x){
    
	int k=(x%N+N)%N;
	e[++cnt].to=x;
	e[cnt].next=h[k];
	h[k]=cnt;
}
bool find(int x){
    
	int k=(x%N+N)%N;
	for(int i=h[k];i;i=e[i].next){
    
		if(e[i].to==x)return true;
	}
	return false;
}
int main(){
    
	int n;
	cin>>n;
	char op;
	int x;
	while(n--){
    
		cin>>op>>x;
		if(op=='I')insert(x);
		if(op=='Q'){
    
			if(find(x))cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
	
    return 0;
}

Open addressing

One dimensional array , Open to the range of subject data 2~3 times , The minimum prime number greater than twice the search range of the topic

#include<iostream>
#include <string.h>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x){
    
	int k=(x%N+N)%N;
	while(h[k]!=null&&h[k]!=x){
    
		k++;
		if(k==N)k=0;
	}
	return k;
}
int main(){
    
	int n;
	cin>>n;
	char op;
	int x;
	memset(h,0x3f,sizeof(h));	
	while(n--){
    
		cin>>op>>x;
		if(op=='I')h[find(x)]=x;;
		if(op=='Q'){
    
			if(h[find(x)]==null)cout<<"No"<<endl;
			else cout<<"Yes"<<endl;
		}
	}
	
    return 0;
}

String hashfa

String prefix hashing
Preprocess the hash of all prefixes
How to define the hash value of each prefix
Think of it as a p Hexadecimal number , Convert strings to spoof numbers

1、 You cannot map a character to 0, Otherwise, there will be a conflict
A——0
AA——0
2、 It is assumed that there will be no conflict
Empirical value
P=131、13331
$Q=2^{64}$
So take $99.9$ There will be no conflict
The previous hash can tolerate conflicts and then handle conflicts ,
The string hash assumes that there is no conflict due to personality explosion , Don't consider conflicts
3、 Use prefix hash to calculate the hash value of all substrings through formula

( String hash ) O(n)+O(m)O(n)+O(m)
Full name string prefix hashifa , Turn a string into a p Hexadecimal Numbers （ Hash value ）, Mapping different strings to different numbers . To form such as
$X1X2X3\cdots Xn-1XnX1X2X3\cdots Xn-1Xn$ String , In characters ascii Code times P To the power of .

Mapping formula $(X1\times Pn-1+X2\times Pn-2+\cdots +Xn-1\times P1+Xn\times P0)modQ$ Be careful ：

1. Any character cannot be mapped to 0, Otherwise, different strings will be mapped to 0 The situation of , such as A,AA,AAA All are 0
2. The question of conflict ： Through clever settings P (131 or 13331) , Q (264)(264) Value , Generally, it can be understood that there is no conflict .

The problem is to compare whether the substrings of different intervals are the same , Whether the corresponding hash value is the same .
Finding the hash value of a string is equivalent to finding the prefix and , Finding the hash value of the substring of a string is equivalent to finding the partial sum .

Prefixes and formulas $h[i+1]=h[i]\times P+s[i]h[i+1]=h[i]\times P+s[i]i\in [0,n-1]i\in [0,n-1]$
h Prefix and array ,s For string array Interval and formula
$h[l,r]=h[r]-h[l-1]\times Pr-l+1h[l,r]=h[r]-h[l-1]\times Pr-l+1$

Understanding of intervals and formulas : ABCDE And ABC The first three character values of are the same , Just two , Multiply P2P2 hold ABC Turn into ABC00, Reuse ABCDE - ABC00 obtain DE Hash value of .

author ：chocolate-emperor link ：https://www.acwing.com/solution/content/24738/
source ：AcWing

841. String hash (kmp A special form of ）

Given a length of n String , Re given m A asked , Each query contains four integers $l1,r1,l2,r2$, Please judge $[l1,r1]and[l2,r2]$ Whether the strings and substrings contained in these two intervals are exactly the same .

The string contains only uppercase and lowercase English letters and numbers .

Input format
The first line contains integers n and m, Represents the length of the string and the number of queries .

The second line contains a length of n String , The string contains only uppercase and lowercase English letters and numbers .

Next m That's ok , Each line contains four integers $l1,r1,l2,r2$, Indicates the two intervals involved in a query .

Be careful , The position of the string is from 1 Numbered starting .

Output format
Output a result for each query , If two string substrings are identical, output Yes, Otherwise output No.

Each result takes up one line .

Data range
$1\le n,m\le 10^5$
sample input ：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
sample output ：
Yes
No
Yes

#include<iostream>
#include <string.h>
using namespace std;
const int N=1e5+7,P=131;// The result of string hash value is very large and needs to be correct 2^64 modulus  
typedef unsigned long long ULL;//unsigned long long 64 position  
ULL p[N];//p[i] Express P Of i The next power , Pretreat and store  
ULL h[N];
char str[N];
ULL get(int l,int r){
    
	return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    
	int n,m;
	cin>>n>>m;
// for(int i=1;i<=n;i++){
    
// cin>>str[i];
// }
	cin>>str+1;
	p[0]=1;
	// Cannot be mapped to 0, So the hash table array is subscript 1 At the beginning  
	for(int i=1;i<=n;i++){
    
		p[i]=p[i-1]*P;
		h[i]=h[i-1]*P+str[i]; // Lowercase letters 97-122
	}
	int l1,r1,l2,r2;
	while(m--){
    
		cin>>l1>>r1>>l2>>r2;
		if(get(l1,r1)==get(l2,r2))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
    return 0;
}