從上一屆已經講了字符串hash的方法，hash后怎么用也很重要

文章目錄

• • 一.查詢子串的hash值
  • 查詢子串減去期中一個字符后的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); }

總結

以上是生活随笔為你收集整理的字符串hash（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。