String hash, find the string hash value after deleting any character, double hash

subject

https://ac.nowcoder.com/acm/contest/1076/G
Title Description
Here are two strings of lowercase letters S,T, Guarantee S The length of alpha is greater than or equal to alpha T, Now you have to delete T One character in the string , bring T String into S The substring of a string , Output the deleted location , If there are multiple legal positions , The one with the smallest output , If there is no legal location , Output -1
Input description :
The first line of input string $S（2<=|S|<=3e^5）$

The second line of input string $T（2<=|T|<=S）$
Output description :
Output a number

Example 1
Input

aaaab
aabaa

Output
3

Example 2
Input

aaaa
aaa

Output
1

Example 3
Input

abcd
xyz

Output
-1

Ideas ：

Simple hash , hold s The continuous length in the string is len_t-1 The substring of is converted to the corresponding value , Deposit in map in ; And then t Take each character out of the string , Convert a substring with one character removed into a numeric value , if map If there is such a value in, the legal answer is found .

#include<iostream>
#include<map>
#include <string.h>
using namespace std;
const int N=3e5+10,P=131;
typedef unsigned long long ULL;
char s[N];
char t[N];
ULL hs[N];
ULL ht[N];
//int p[N]; Just test a set of data , Fast exponentiation is good , Not all pretreatment , It takes too much time 
ULL quickpow(ULL b,ULL e){
    
// The data type of the parameter must always be the same as the return value ,int There must be a mistake  , About the data characteristics of fast power ？ 
	ULL res=1;
	while(e){
    
		if(e&1)res*=b;
		b*=b;
		e>>=1;
	}
	return res;
} 
ULL getHs(int l,int r){
    
	if(l>r)return 0;
	return hs[r]-hs[l-1]*quickpow(P,r-l+1);
} 
ULL getHt(int l,int r){
    
	if(l>r)return 0;
	return ht[r]-ht[l-1]*quickpow(P,r-l+1);
} 
map<ULL,int> mp;
int main(){
    
	cin>>s+1>>t+1;
	int ls=strlen(s+1);
	int lt=strlen(t+1);
// p[0]=1;
	for(int i=1;i<=ls;i++){
    
// p[i]=p[i-1]*P;
		hs[i]=hs[i-1]*P+s[i];
	}
	for(int i=1;i<=lt;i++){
    
		ht[i]=ht[i-1]*P+t[i];
	}
	for(int i=1;i<=ls-lt+1;i++){
    
// Only according to s The length of the prefix hash value of is lt-1 The hash of the substring of is ok ls-(lt-1) 
		mp[getHs(i,i+lt-2)]=1;//i+(lt-1)-1
	}
// for(int i=lt-1;i<=ls;i++){ 
// ULL k=hs[i]-hs[i-lt+1]*quickpow(P,lt-1);
// mp[k]=1;
// }

// enumeration t Delete in t[i] Hash value of ,ht[1->i-1]+ht[i+1,lt]
	for(int i=1;i<=lt;i++){
    
		ULL k=ht[i-1]*quickpow(P,lt-i)+getHt(i+1,lt);
		//！！！ The hash value of the string after the splicing of two strings is not directly added , First fill the previous string 0 
		if(mp[k]==1){
    
			cout<<i;
			return 0;
		}
	}
	cout<<"-1";
    return 0;
}

Find the string hash value after deleting any character

ULL k=ht[i-1]*quickpow(P,lt-i)+getHt(i+1,lt);

How to calculate the hash value after changing the original string by several letters .（ But there is one limitation , When hashing a string , There's only one variable , Instead of opening an array to record the hash value of each bit ）

If you push the formula, don't push , Just record the formula results ：
First, specify the subscript of the string from 1 Start , The string length is len, The elements that change are s[i], take s[i] To be changed to c

$h=h+(c-s[i])\ast p^{(len-i)};$

Double hash

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
char s[maxn],t[maxn];
long long  base[3]={
    0,23,29},mod[3]={
    0,100000000+7,100000000+9},h[3][maxn],f[3][maxn];
map<long long,int >mp_1,mp_2;
long long ksm(long long res,long long cnt,long long mo)
{
    
    long long  sum=1;
    while(cnt>0)
    {
    
        if(cnt&1)sum=(sum*res)%mo;
        res=(res*res)%mo;
        cnt>>=1;
    }
    return sum;
}
int main()
{
    
	//memset(h,0,sizeof(h));
	//memset(f,0,sizeof(f));
    scanf("%s%s",s+1,t+1);
    int len_s=strlen(s+1);
    int len_t=strlen(t+1);

    for(int i=1;i<=len_s;i++)
    {
    
    	for(int k=1;k<=2;k++)
    	h[k][i]=(h[k][i-1]*base[k]+s[i]-'a'+1)%mod[k];
        
    }
    long long res[3];
    for(int i=len_t-1;i<=len_s;i++)
    {
    
    	for(int k=1;k<=2;k++)
    	res[k]=(h[k][i]-h[k][i-len_t+1]*ksm(base[k],len_t-1,mod[k])%mod[k]+mod[k])%mod[k];
    	mp_1[res[1]]=1;
    	mp_2[res[2]]=1;
    	
	}
	
    for(int i=1;i<=len_t;i++)
    {
    
        for(int k=1;k<=2;k++)
         f[k][i]=(f[k][i-1]*base[k]+t[i]-'a'+1)%mod[k];
    }
    
    
    for(int i=1;i<=len_t;i++)
    {
    
        for(int k=1;k<=2;k++)
            res[k]=(f[k][len_t]-f[k][i]*ksm(base[k],len_t-i,mod[k])%mod[k]
			        +f[k][i-1]*ksm(base[k],len_t-i,mod[k])%mod[k]+mod[k])%mod[k];
        if(mp_1[res[1]]==1&&mp_2[res[2]]==1)
        {
    
            cout<<i;
            return 0;
        }
    }
            
    cout<<-1<<endl;  
        
    

}

Double hash template

Double hash is a conflict resolution scheme in open address hash , That is to say, if one hash cannot solve the problem , To hash again , Different from the rehash method , The hash function used for the second time is different from that used for the first time ：

https://www.cnblogs.com/energy1010/p/5802942.html

#include <iostream>
usinh namepace std;
typedef long long ll;
const int N=1e6+10;
const int mod1=1e9+7;// If there is any error, modify it manually 
const int mod2=1e9+9;
ll has1[N],has2[N];
ll bas1[N],bas2[N];// If you use quickpow Don't use this , It mainly depends on the data range , Decide whether to preprocess or fast power  
const int p1=131,p2=13331;
// has1[0]=has2[0]=0;// Hash value cannot be 0, Subscript from 1 Start  
    bas1[0]=bas2[0]=1;
    int len=strlen(s+1);
    for(int i=1;i<=len;++i){
    // Multiple strings hash It can be pretreated 
        bas1[i]=(bas1[i-1]*p1)%mod1;
        bas2[i]=(bas2[i-1]*p2)%mod2;
    }
    for(int i=1;i<=len;++i){
    
        has1[i]=(has1[i-1]*p1+s[i])%mod1;
        has2[i]=(has2[i-1]*p2+s[i])%mod2;   
    }
}
ll gethash1(int r,int len){
    // Return to r End length len The string of has1 value 
    return ((has1[r]-has1[r-len]*bas1[len])%mod1+mod1)%mod1;
}
ll gethash2(int r,int len){
    // Return to r End length len The string of has2 value 
    return ((has2[r]-has2[r-len]*bas2[len])%mod2+mod2)%mod2;
ll gethash11(int l,int r){
    // The length is  r-l+1 
    return ((has1[r]-has1[l-1]*bas1[r-l+1])%mod1+mod1)%mod1;
}
ll gethash22(int l,int r){
    // The length is  r-l+1 
    return ((has2[r]-has2[l-1]*bas2[r-l+1])%mod2+mod2)%mod2;

Open two map Container two pronged , But in the same container, if the hash value of the corresponding main string and the hash value of the mode string , That is, the hash value mapped by the same hash function , To judge the equality of strings according to the equality of hash values