从上一届已经讲了字符串hash的方法，hash后怎么用也很重要

文章目录


**hash的模板（自然溢出）** 
char s[10010];
ull hashs(char s[])
{
   
	int len=strlen(s);
	ull base=131;
    ull head[]=0;
    for (int i=1;i<=len;i++)
        head[i]=head[i-1]*base+(ull)s[i];
        
    return ans&0x7fffffff;//舍弃符号位
}

一.查询子串的hash值

base[x]表示base的x此方
head[1]=s1
head[2]=s1base[1]+s2
head[3]=s1base[2]+s2*base[1]+s3
…
我们可以得到：
字符串S中子串[l，r]的hash值为：
hash=hash[r]-hash[l-1]*base[r-l+1]

unsigned long long get_hash(int l, int r)
{
   
        return hash[r] - hash[l-1] * base[r-l+1];
}

查询子串减去期中一个字符后的hash值

查询字符串S中范围[l,r],但是去掉区间中坐标为x的字符串，问剩下的hash
其实就是将 [ l , r ] 分解成 [ l , x - 1 ] [x+1,r ],求这两块的hash
扩展一下，去掉哪里你就把区域在这里给拆开就行，分着求最后合在一起

但是注意，因为中间被你挖去一块，也就是 [ l , x - 1 ] 与 [ x+1,r ]并不是相连的，他们两个的hash值不能直接相加，很简单因为他们都是因为base的倍数乘积所以相连，所以讲前者（也就是[ l , x - 1 ] ）强行左移r-x位（以base的进制），左移就是乘base的r-x次方
位移次数是右区间左端点与右端点之间的数量r-(x+1)+1

unsigned long long get_hash_delete(int l, int r, int x)
{
   
    return get_hash(l, x-1) * base[r-x] + get_hash(x+1, r);
}

多用以求最长回文子串或者回文子串数量，当然manacher、kmp能完成的更好

查询两个子串拼接的hash值

其实拼接和去除原理是一样的
拼接不就是去除倒嘛
所以代码原理和上面也差不多，两个区域[l,r]和[x,y]的哈希值，前者通过位移使得两个区域可以直接相加，位移的次数就是y-x+1(其实和上面一样的，你细品)

unsigned long long get_s1_s2(int l, int r, int x, int y)
{
   
    return get_hash(l, r) * p[y-x+1] + get_hash(x, y);
}