ACM模板

---

目錄

• • • 構(gòu)建
    • 應(yīng)用

構(gòu)建

字符串哈希就是將字符串映射成一個(gè)數(shù)，哈希沖突是不可避免的，我們需要選用合適的base盡可能使得哈希沖突可能性降低

unsigned long long溢出后相當(dāng)于取模，相當(dāng)于模$2^{64}?1$

get(l,r)函數(shù)返回字符串下標(biāo)[l,r]的哈希值

typedef unsigned long long ull; const int N=100010,P=131;//13331 19260817 防止哈希沖突 ull h[N],p[N]; ull get(int l,int r) {return h[r]-h[l-1]*p[r-l+1]; } void build(char s[]) {int n=strlen(s+1);p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+str[i]-'a'+1;} }

應(yīng)用

• 暴力字符串匹配
• 優(yōu)化字符串字典序比較——二分+哈希：通常可以二分最長(zhǎng)公共前綴，然后比較公共前綴的下一個(gè)字符即可以知道字典序。
• log求最長(zhǎng)回文串：首先將原串和逆序串哈希，枚舉回文中心，二分回文半徑
• 記錄一些dp的狀態(tài)

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【模板】字符串哈希的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。