又來寫演演算法總結了qwq。
今天是 2023/7/8，期末考試已經考完了。初二下注定是一個煎熬的學期，所以我在這一學期並沒有學什麼新演演算法，OI 也沒什麼長進。但倒是深造了幾個演演算法，比如：dp，hash，線段樹。
之前一直想寫一篇 hash 的學習筆記，但由於種種原因，並沒有寫成。於是，就在今天，卷完了一天的 whk 過後，我便開始肝 hash 的學習筆記。
本篇主要介紹 hash 的進階用法，不過也適合 hash 入門（不知道哪來的自信）。如果寫假了，就圖一樂子qwq。
感謝 @ben093002 對此學習筆記給予結論證明以及鼓勵與支援！
好了，正片開始！
雜湊演演算法（Hash Algorithm），又稱雜湊演演算法。有兩種用法，第一種就是將一字串轉化成任意進位制的數，目的是方便儲存。第二種就是將大範圍的數對映成小範圍的數，目的也是方便儲存。
用第一種打一個比方：
比如要將 ioiakyzy 轉成 29 進位制的數：
將每一位字母偏移，設偏移量為字母 a 所對應的 ASCLL碼 - 1，則字母 a 的原數為 1，字母 b 的原數為 2，字母 c 的原數為 3，\(\dots\)，以此類推；
通過 1 可知，原字串可轉化為 9(15)91(11)(25)(26)(25)；
將 9(15)91(11)(25)(26)(25) 轉成 29 進位制數：
所以 ioiakyzy 在 29 進位制下的 hash 值為 164356834301。
操作 1 的 「字母偏移」 完全可以不需要，設偏移量僅僅是使雜湊值的值域變小，方便儲存而已。
第二種的話就不用所說了，因為第二種就是我們熟知的離散化，c++ 的 STL 庫中的 map 就有體現。
離散化嚴格意義上是一種雜湊。
在做字串轉雜湊值的時候可能會發生一些突發狀況。比如雜湊值太大了，long long 已經裝不下了。怎麼辦？第一時間會想到對此雜湊值取模。但萬一有兩個不同的字串所轉出來的雜湊值取模過後相同，那可就麻煩了。因為這樣，在進行對字串雜湊的一系列操作時正確性無法保證了。
這時，就有兩種處理方法：
證明法1的可行性：（模數為質數）
設 \(mod1 < mod2\)，且 \(mod1 = mod2 - x (x \in \mathbb{N^+})\)
因為 \(p1 \in \mathbb{N^+}，\forall p1\in [0,mod1-1] \pmod{mod1}\)
且 \(p2 \in \mathbb{N^+}，\forall p2\in [0,mod2-1] \pmod{mod2}\)
所以，在模 \(mod1\) 意義下的雜湊值衝突的概率為 \(\sum\limits_{i=1}^n\dfrac{1}{mod1^2}=\dfrac{mod1}{mod1^2}=\dfrac{1}{mod1}\)，模 \(mod2\) 意義下下的雜湊值衝突的概率為 \(\dfrac{1}{mod2}\)
因為 \(mod1 < mod2\)，所以 \(\dfrac{1}{mod1} > \dfrac{1}{mod2}\)。
所以模數越大，雜湊衝突的概率越小。
證畢。
證明法2的可行性：（模數為質數）
設 \(n1 < n2\)，且有 \(mod1_1,mod1_2, mod1_3, \dots, mod1_{n1}\) 和 \(mod2_1, mod2_2, mod2_3, \dots, mod2_{n2}\) （\(\forall i \leq n1,mod1_i \in \mathbb{N^+}\)，\(\forall j \leq n2,mod2_j \in \mathbb{N^+}\)，\(\forall mod1_i \ne \forall mod2_i\)）
由證明1可知，模 \(mod1\) 意義下的雜湊值值域為 \(\prod\limits_{i=1}^{n1}mod1_i\)，模 \(mod2\) 意義下下的雜湊值值域為 \(\prod\limits_{i=1}^{n2}mod2_i\)
所以，模 \(mod1\) 意義下的雜湊值衝突的概率為 \(\dfrac{1}{\prod\limits_{i=1}^{n1}mod1_i}\)，在模 \(mod2\) 意義下的雜湊值衝突的概率為 \(\dfrac{1}{\prod\limits_{i=1}^{n2}mod2_i}\)
因為 \(\prod\limits_{i=1}^{n1}mod1_i < \prod\limits_{i=1}^{n2}mod2_i\)，所以 \(\dfrac{1}{\prod\limits_{i=1}^{n1}mod1_i} > \dfrac{1}{\prod\limits_{i=1}^{n2}mod2_i}\)
所以，模數越多且互不相同的情況下，雜湊衝突的概率越小。
證畢。
在 2.1 的一系列證明中都加了一句話：模數為質數。說明模數為質數很重要。
事實也是如此，如果模數為合數，雜湊衝突的概率會增加，具體的證明可以看這裡。不過沒看懂也沒關係，這並不影響雜湊的學習。就像學習並查集（路徑壓縮 + 按秩合併）的時候你也不會證明其時間複雜度。
但是要注意，雜湊更像是一種騙分的工具，因為它有許多的不確定性在裡面，跟模擬退火差不多（或者你寫雜湊的時候不用模數）。
字串雜湊是一種很常見的雜湊函數。
現在給你一個問題：給定兩個字串 \(S\)，\(T\)，長度別為 \(n\), \(m\)。求 \(T\) 是否是 \(S\) 的子串。
暴力做法很簡單，掃 \(S\)，\(T\) 再 check 即可。時間複雜度 \(O(nm)\)。
其實還能更優，用 KMP 演演算法可以做到 \(O(n)\)。
但 KMP 不會怎麼辦。用雜湊！！
設 \(sum_i\) 表示字串 \(S\) 子串 \([1, i]\) 的雜湊值。結合 1.2 對雜湊的概論，可得：
設雜湊進位製為 \(H\)，模數為 \(mod\)。可得字串 \(S\) 的子串雜湊通項公式為 $sum_i = \sum\limits_{j=1}^i S_j \times H^{i-j} $
遞推式為：
\(\begin{cases}sum_0=0\\sum_i=sum_{i-1}*H+S_i\end{cases}\)
程式碼實現：
sum[0] = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i-1] * H + S[i] % mod;
}
OK！雜湊預處理完成。
現在可以用 \(sum\) 這個字串雜湊做很多很多的操作，比如：
怎樣擷取子串雜湊值呢？手推一下就行了。
擷取 \([l,r]\) 的雜湊值，可以類比字首和。
\(\sum_{i=l}^r s_i \times H^{r-i}\)
\(= H^{r-i} \times (\sum_{i=1}^r s_i - \sum_{i=1}^{l-1} s_i)\)
\(= \sum_{i=1}^r s_i \times H^{r-i} - \sum_{i=1}^{l-1} s_i \times H^{r-i}\)
\(= \sum_{i=1}^r s_i \times H^{r-i} - H^{r-l+1} \times \sum_{i=1}^{l-1} s_i H^{l-i-1}\)
\(= sum_r - sum_{l-1} \times H^{r-l+1}\)
所以 \([l,r]\) 的雜湊值為 \(sum_r - sum_{l-1} \times H^{r-l+1}\)。
不過 \(H^{r-l+1}\) 要快速冪，太麻煩了。所以直接預處理一下 H 的任意次方即可。
由於可能會減出負數，所以減完之後先加mod再模mod就行了。具體實現看程式碼。
時間複雜度 \(O(1)\)。
程式碼實現：
預處理
int p[N] = {0};
for (int i = 1; i <= n; i++) {
p[i] = p[i-1] * H % mod;
}
擷取子串
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
很簡單，只要結合擷取子串操作便能完成。
時間複雜度 \(O(1)\)。
程式碼實現：
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
bool check(int l, int r, int L, int R) {
return get(l,r) == get(L,R);
}
回到最初的問題：給定兩個字串 \(S\)，\(T\)，長度別為 \(n\), \(m\)。求 \(T\) 是否是 \(S\) 的子串。
這下不就很簡單了嗎？
核心程式碼實現：
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
int main() {
int n, m, sum[N], SUM[N];
char S[N], T[N];
cin >> n >> m;
cin >> S + 1 >> T + 1;
sum[0] = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i-1] * H + S[i] % mod;
}
for (int i = 1; i <= m; i++) {
SUM[i] = SUM[i-1] * H + T[i] % mod;
}
for (int i = 1; i + m - 1 <= n; i++) {
if(get(i, i + m - 1) == SUM[m]) puts("Yes");
else puts("No");
}
return 0;
}
假如你忘記了馬拉車，kmp等字串演演算法怎麼寫了，不妨試一試字串雜湊。
還有就是你可以用其優化 dp，比如這一道題 —— gym104081，可以試著做一做，做完後可能你會對字串雜湊有更深刻的理解。
容錯率較高，但相對來說程式碼易實現。
具體證明可參考 2.2 如何解決雜湊衝突 這一章的相關證明。
發現單雜湊在某種情況下會寄掉。這時使用雙雜湊是最好的選擇。
可以證明，模數增多可以降低雜湊的容錯率（衝突概率），此在上文已經證明。
不過寫多重雜湊可能會導致空間承受不起（不過你不寫雜湊表就沒有關係）。所以，正常雜湊不建議寫模數數量大於二的雜湊。
可以證明，當模數增加一個，離散值域會增加一倍，容錯率便會大大下降。
具體實現為用一個 \(pair\) 。第一維記錄在模第一個模數的意義下的雜湊值，第二維記錄在模第二個模數的意義下的雜湊值。當兩維都對應相等時，雜湊值才有可能相等。（其實根本不需要證明，感性理解一下也可以）。
你還在因為選不定模數而煩惱嗎？你還在因為每次計算都要取模而煩惱嗎？
有了自然溢位，你還在擔心什麼？
如果你把儲存雜湊值的陣列的資料型別改成 unsigned long long。首先，這個東西不支援儲存負數，處理方法為將雜湊值模一個超大的非素數，使其不會爆 \(long long\) 的符號位。
其實這一步就相當於再給雜湊取模的過程。不僅短而好寫，而且很簡單，每次計算不需要模數。
必須注意的是，自然溢位模的數不是質數這意味著它的衝突率高於質數，不過，由於這個模數足夠大，所以可忽略這點區別。
不過缺點就是麻仁，CF 卡這玩意卡出了花樣。（在 CF 和 AT 手上自然溢位容錯率接近於 \(100\%\)）
其實原理很簡單，就是我們要記錄每一個已經誕生的雜湊值，然後對於每一個新的雜湊值，我們都可以來判斷是否和已有的雜湊值衝突，如果衝突，那麼可以將這個新的雜湊值不斷加上一個大質數，直到不再衝突。
比如這一題：P3370 【模板】字串雜湊
就用一個 vector 儲存每一次衝突的雜湊值，再暴力掃即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <string>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define mod 1000003
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 100010;
int n = read(), x, ans;
string s;
vector <string> h[mod];
bool F(int x, const string &s) {
for (auto t : h[x]) {
if(t == s) return 0;
}
h[x].push_back(s);
return 1;
}
signed main() {
For(i,1,n) {
cin >> s;
x = 0;
For(j,0,s.size()-1) {
x = (1ll * x * H + s[j]) % mod;
}
ans += F(x, s);
}
cout << ans << '\n';
return 0;
}
桶雜湊的本質是一個「桶」，這個桶很特殊，接下來看看普通桶和桶雜湊的時間複雜度區別：
| 操作 | 普通桶 | 桶雜湊 |
|---|---|---|
| 單點修改 | \(O(1)\) | \(O(1)\) |
| 區間修改 | \(O(n)\) | 最壞\(O(n)\) |
| 單點查詢 | \(O(1)\) | 不支援 |
| 區間查詢 | \(O(n)\) | 不支援 |
| 全域性查詢 | \(O(n)\) | \(O(1)\) |
這樣，桶雜湊和普通桶的優勢與劣勢顯而易見。
Q：啊？這樣看來，普通桶大勝桶雜湊？
是的，這樣看來，普通桶大勝桶雜湊。但換個角度看就不是了：桶雜湊實現起來困難，常數大，且正確率不能保障，但全域性查詢為 O(1)。
不過，它也不是一無是處。如果它的全域性查詢可以做到 \(O(1)\)。這也證明，桶雜湊可以在一些特殊的題中扮演決定性的角色。
比如，桶雜湊可以 \(O(1)\) 的時間比較兩個桶的狀態。但是普通的桶做到這一點要 \(O(n)\)。
其實有一個兩者的綜合版——權值線段樹。它的單點/區間修改/查詢單次時間複雜度為 \(O(\log n)\)，可謂是非常的優秀！
桶雜湊：啊？？真的如此嗎？。
設 \(b\) 桶雜湊第 \(i\) 位表示 \(i\) 這個數的出現的次數，\(H\) 為進位制。\(x\) 為我要在桶中插入的數。
於是就仿照二進位制狀壓的寫法，\(b = b + H^{x}\)。然後就沒了。
Code:
b += p[x];
ps: 省去了取模操作，\(p_i\) 為預處s理好的 \(H^i\) 的值。
如果要插入多個數，則在 \(p_x\) 前面乘上一個係數即可。
重複單點修改操作，時間複雜度為 \(O(n)\)。
但是有些時候區間修改的只是固定的，便可考慮離線記錄改變的值。這樣可以做到期望 \(O(1)\)。
比如我要說的下一道題目。
分析得：每一個點的入度都為 \(1\)，則輸出 "YES"，否則輸出："NO"。
設一個標準桶 \(POS\) 為 \(111\dots11\) 這樣的全 \(1\) 桶。設第 \(i\) 個點的入度為 \(r_i\)，實際桶 \(Hash\) 為當前所有節點的入度個數，顯然其長度為 \(n\)，初始第 \(i\) 位為 \(r_i\)。在一次操作後只要 \(POS = Hash\)。則說明其合法。
這一步就體現了桶雜湊的強大之處——全域性查詢為 \(O(1)\) 時間複雜度。
最後附上程式碼：
#include <bits/stdc++.h>
#define ll long long
#define H 500005
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000000007
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 5e5 + 10;
vector<int> e[N];
ll n, m, q, p[N], POS, Hash, sum[N], rem[N], r[N];
signed main() {
n = read(), m = read();
p[0] = 1;
For(i,1,n) {
p[i] = (p[i - 1] * H) % MOD;
}
For(i,1,n) POS = POS + 1 * p[i];
For(i,1,m) {
int u = read(), v = read();
e[u].push_back(v);
r[u]++;
}
For(i,1,n) {
for (int j = 0; j < e[i].size(); j++) {
int y = e[i][j];
sum[y] += p[i];
}
}
For(i,1,n) rem[i] = sum[i], Hash += sum[i];
q = read();
while(q--) {
int op = read();
if(op == 1) {
int u = read(), v = read();
Hash -= p[u];
rem[v] -= p[u];
} else if(op == 3) {
int u = read(), v = read();
Hash += p[u];
rem[v] += p[u];
} else if(op == 2) {
int u = read();
Hash -= rem[u];
rem[u] = 0;
} else {
int u = read();
Hash -= rem[u] - sum[u];
rem[u] += sum[u];
}
if(Hash == POS) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
給定若干個字串 \(S\), 對於每一個字串，要求選取他的一個字首（可以為空）和與該字首不相交的一個字尾（可以為空）拼接成迴文串，且該回文串長度最大。求生成的最長迴文串是什麼。
可以先做一下小小的分類討論：
若 \(S\) 有迴文前字尾，並且長度相等（比如：abcdfdcecba，abccba就是長度相等的迴文前字尾），那麼，肯定取這一段前字尾最優。
把 \(s\) 的迴文前字尾拿掉後，剩下的部分要麼是迴文字首，要麼是迴文字尾。再把其中長度較長的拼接再回文前字尾的中間即可。
比如：abcdfdcecba，先找出其迴文前字尾abccba，剩下的部分為 dfdce，發現有一個迴文字首 dfd，於是把其插入 abccba 的中間，最後答案為：abcdfdcba
再比如：abbaxyzyx，它沒有迴文前字尾，於是要找回文字首或字尾就行了。答案為：xyzyx。
找回文前字尾可以用雙指標，找回文字首或字尾可以用 hash，時間複雜度 \(O(Tn)\)，也就是 \(O(\sum |S|)\)。
#include <bits/stdc++.h>
#define int long long
#define H 449
#define rint register int
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define mod 436522843
using namespace std;
const int N = 1e6 + 10;
int T, n, sum[N], pre[N], p[N];
char a[N];
void solve() {
cin >> a + 1;
n = strlen(a + 1);
p[0] = 1;
For(i,1,n) {
p[i] = p[i-1] * H % mod;
}
int l = 0, r = n+1;
while(a[l+1] == a[r-1] && l <= r) {
l++, r--;
}
if(l > r) {
For(i,1,n) cout << a[i];
cout << '\n';
return ;
}
l++, r--;
sum[l-1] = 0, pre[r+1] = 0;
For(i,l,r) {
sum[i] = sum[i-1] * H % mod + (a[i] - 'a' + 1);
sum[i] %= mod;
}
FOR(i,r,l) {
pre[i] = pre[i+1] * H % mod + (a[i] - 'a' + 1);
pre[i] %= mod;
}
int ansl = 0, ansr = 0;
For(i,l,r) {
if(sum[i] == (pre[l] % mod - pre[i+1] * p[i-l+1] % mod + mod) % mod) {
ansl = l, ansr = i;
}
}
FOR(i,r,l) {
if(pre[i] == (sum[r] % mod - sum[i-1] * p[r-i+1] % mod + mod) % mod) {
if(ansr - ansl + 1 < r - i + 1) {
ansl = i, ansr = r;
}
}
}
For(i,1,l-1) cout << a[i];
For(i,ansl,ansr) cout << a[i];
For(i,r+1,n) cout << a[i];
cout << '\n';
}
signed main() {
cin >> T;
while(T--) {
solve();
}
return 0;
}
/*
1
abbaxyzyx
*/
定義若兩個賬戶名稱是相似的，當且僅當這兩個字串等長且恰好只有一位不同。例如「Penguin1」和「Penguin2」是相似的，但「Penguin1」和「2Penguin」不是相似的。求在給定的 \(n\) 個賬戶名稱中，有多少對是相似的。
組合數學 + Hash
預處理出每一個字串的前字尾 \(Hash\)，再列舉每一位，用組合數學統計合法數對就行。
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define H 27
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 3e4 + 10, M = 205;
int n, L, S;
ull pre[N][M], nxt[N][M], p[N], ans;
char s[N][M];
pair<ull, ull> k[N];
signed main() {
n = read(), L = read(), S = read();
p[0] = 1;
For(i,1,L) p[i] = p[i - 1] * H;
For(i,1,n) {
For(j,1,L) cin >> s[i][j];
For(j,1,L) pre[i][j] = pre[i][j - 1] * H + s[i][j];
FOR(j,L,1) nxt[i][j] = nxt[i][j + 1] * H + s[i][j];
}
For(i,1,L) {
For(j,1,n) {
k[j].first = pre[j][i-1];
k[j].second = nxt[j][i+1];
}
sort(k + 1, k + n + 1);
int l = 1, r = 1;
while(r <= n) {
while(k[l] == k[r] && r <= n) r++;
r--;
ans += (((r - l + 1) * (r - l)) >> 1);
l = r + 1, r++;
}
}
cout << ans << '\n';
return 0;
}
給定兩個長度為 \(n\) 的小寫字母串 \(s\) 和 \(t\)。求在不同情況下從 \(s\) 中選出一個子序列與 \(t\) 中選出一個子串對應相同的方案數（兩種情況不同，當且僅當兩序列所選出的字串在兩種情況中不同）。
列舉 \(t\) 的子串，固定左端點 \(L\)，右端點 \(r\) 遞增。同時在 \(s\) 中找是否有子序列與所列舉的字串對應相同。為了方便統計方案數，可以用 \(Hash\) 來判斷兩種情況是否相同。把 \(Hash\) 值丟到 \(unordered\)_\(set\)，\(set\)，或隨便搞一個陣列（之後進行 sort 和 unique）裡面去。實測只有最後一個方法可以通過。
時間複雜度 \(O(N^2\log n)\)。
#include <bits/stdc++.h>
#define int long long
#define H 37
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 3e3 + 10;
const int M = 9e6 + 10;
int n, hs, nxt[N][156], res[M], tot;
char s[N], t[N];
signed main() {
n = read();
For(i,1,n) cin >> s[i];
For(i,1,n) cin >> t[i];
For(i,1,n) {
For(j,i,n) {
if(!nxt[i][s[j]]) nxt[i][s[j]] = j;
}
}
For(i,1,n) {
hs = 0;
int k = 1;
For(j,i,n) {
k = nxt[k][t[j]];
if(!k) break;
hs = 1ll * (hs * H) + (t[j] - 'a' + 1);
res[++tot] = hs;
k++;
}
}
sort(res + 1, res + 1 + tot);
cout << ((unique(res + 1, res + 1 + tot)) - res - 1) << '\n';
return 0;
}