owned this note
owned this note
Published
Linked with GitHub
---
tags: 2023-i2cp
type: slide
slideOptions:
transition: fade;
---
<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# String Algorithm
Introduction to Competitive Programming
2023/04/26
----
- Trie
- Bitwise Trie
- KMP
- Hash
---
## trie
[字典樹](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d) ( or 字首樹 )
----
----
### 範例
[Zerojudge d518](https://zerojudge.tw/ShowProblem?problemid=d518)
給 $N$ 個字串 $s_i$, 依序讀入後輸出
前面是否有出現過此字串 $s_i$, 有出現過的話是第幾次出現的
----
### 結構
<div style="font-size: 30px">
每個節點有往下的指標
以及紀錄多少個字串以此為結尾
</div>
```cpp=
struct trie{
trie *nxt[26];
int cnt; //紀錄有多少個字串以此節點結尾
int sz; //有多少字串的前綴包括此節點
trie():cnt(0),sz(0){
memset(nxt,0,sizeof(nxt));
}
};
//創建新的字典樹
trie *root = new trie();
```
----
### 插入
將字串 $s$ 加入字典樹
```cpp=
// O(|s|)
void insert(string& s){
trie *now = root; // 每次從根結點出發
for(auto i:s){
now->sz++;
if(now->nxt[i-'a'] == NULL){
now->nxt[i-'a'] = new trie();
}
now = now->nxt[i-'a']; //走到下一個字母
}
now->cnt++;
now->sz++;
}
```
----
### 查詢
```cpp=
// O(|s|)
int query_prefix(string& s){ //查詢有多少前綴為 s
trie *now = root; // 每次從根結點出發
for(auto i:s){
if(now->nxt[i-'a'] == NULL){
return 0;
}
now = now->nxt[i-'a'];
}
return now->sz;
}
int query_count(string& s){ //查詢字串 s 出現次數
trie *now = root; // 每次從根結點出發
for(auto i:s){
if(now->nxt[i-'a'] == NULL){
return 0;
}
now = now->nxt[i-'a'];
}
return now->cnt;
}
```
---
## bitwise trie
01 trie
本質也是 trie，用在跟 xor 有關的題目
看到 xor 的難題，有約 50% 是用 trie 解
將數字轉成二進位後存成 trie
----
## bitwise trie
看題目限制換成二進位最多會有幾個位元
每個數字換成二進位從最高的位元開始儲存
----
### 結構
```cpp=
struct trie{
trie *nxt[2]; // 差別
int cnt; //紀錄有多少個數字以此節點結尾
int sz; //有多少數字的前綴包括此節點
trie():cnt(0),sz(0){
memset(nxt,0,sizeof(nxt));
}
};
//創建新的字典樹
trie *root = new trie();
```
----
### 插入
將數字 $x$ 加入字典樹，$O(\log x)$
```cpp=
void insert(int x){
trie *now = root; // 每次從根節點開始
for(int i=30;i>=0;i--){ // 從最高位元開始往低位元走
now->sz++;
if(now->nxt[x>>i&1] == NULL){ //判斷當前第 i 個位元是 0 還是 1
now->nxt[x>>i&1] = new trie();
}
now = now->nxt[x>>i&1]; //走到下一個位元
}
now->cnt++;
now->sz++;
}
```
----
### 引入問題
一開始給 $N (N \le 10^5)$ 個數字
$Q (Q \le 10^5)$ 筆詢問，每次給你兩個數字 $v, d$
問序列中有多少個數字 xor $v$ 後 $\le d$
----
詢問多少個數字 xor $4$ 之後小於等於 $5$
----
----
----
----
----
### 區間最大 xor
給長度為 $N$ 的整數序列, 求出一個子區間其 xor 總和最大
- $1\le N\le 2\cdot 10^5$
----
先回到更簡單的題目, 給一個整數序列 $a$ 和整數 $d$
詢問序列中哪個數字與 $d$ xor 後最大?
此問題我們可以把先把 $a$ 中的所有數字丟進去 trie 裡面,
再 greedy 的每次往 xor 比較大的那邊走
----
而要求出區間最大 xor, 等價於把對於每個位置當右界
找出每個位置前綴 xor 中最大的那個
使用 trie 維護所有前綴總和即可
所有之中最大的為答案
---
## Knuth–Morris–Pratt algorithm
### (KMP)
給定一個原始字串 `S`，求出單字 `W` 在字串 `S` 中所有出現的位置
$1 \le$ | `W` | $\le$ | `S` | $\le 10^6$
----
## 暴力作法
`O(|S|*|W|)`
依序窮舉 `S` 每個位置為開頭的字串，花 `O(|W|)` 時間比對字串是否相同
----
## Hash 作法
每個位置為開頭比對長度為 $|W|$ 的子字串是否相同
複雜度 $O(N)$
----
### KMP
<div style="font-size:60px">
`S` = ababcababcabd
`W` = abcabd
</div>
----
比對第一個字元相同
<div style="font-size:60px">
`0123456789012`
<span style="color:green">`a`</span>`babcababcabd`
<span style="color:green">`a`</span>`bcabd`
`^`
</div>
----
比對第二個字元相同
<div style="font-size:60px">
`0123456789012`
<span style="color:green">`ab`</span>`abcababcabd`
<span style="color:green">`ab`</span>`cabd`
`^`
</div>
----
比對第三個字元相異
<div style="font-size:60px">
`0123456789012`
<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcababcabd`
<span style="color:green">`ab`</span><span style="color:red">`c`</span>`abd`
`^`
</div>
----
把 `W` 字串往右一格重新比對，比對失敗
<div style="font-size:60px">
`0123456789012`
`a`<span style="color:green"></span><span style="color:red">`b`</span>`abcababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`a`</span><span style="color:red"></span>`bcababcabd`
<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
比對第二格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`ab`</span><span style="color:red"></span>`cababcabd`
<span style="color:green">`ab`</span><span style="color:red"></span>`cabd`
`^`
</div>
----
比對第三格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abc`</span><span style="color:red"></span>`ababcabd`
<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
`^`
</div>
----
比對第四格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abca`</span><span style="color:red"></span>`babcabd`
<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
`^`
</div>
----
比對第五格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red"></span>`abcabd`
<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
`^`
</div>
----
比對第六格相異
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">`abcab`</span><span style="color:red">`d`</span>
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`aba`<span style="color:green"></span><span style="color:red">`b`</span>`cababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`abab`<span style="color:green"></span><span style="color:red">`c`</span>`ababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">`a`</span><span style="color:red"></span>`babcabd`
<span style="color:green">a</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
第二格相同
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red"></span>`abcabd`
<span style="color:green">ab</span><span style="color:red"></span>`cabd`
`^`
</div>
----
第三格相異
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">ab</span><span style="color:red">`c`</span>`abd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`ababca`<span style="color:green"></span><span style="color:red">`b`</span>`abcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">a</span><span style="color:red"></span>`bcabd`
<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
第二格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">ab</span><span style="color:red"></span>`cabd`
<span style="color:green">`ab`</span><span style="color:red"></span>`cabd`
`^`
</div>
----
第三格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
`^`
</div>
----
第四格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
`^`
</div>
----
第五格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
`^`
</div>
----
第六格相同，找到一組解
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">`abcabd`</span><span style="color:red"></span>
<span style="color:green">`abcabd`</span><span style="color:red"></span>
`^`
</div>
----
會發現過程中，有很多不必要的匹配
----
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">`abcab`</span><span style="color:red">`d`</span>
`^`
</div>
----
<div style="font-size:60px">
`0123456789012`
aba<span style="color:green"></span><span style="color:red">`b`</span>`cababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
每次失敗就要重頭開始嘗試匹配
----
在匹配失敗時，前面已經有一段不用重新匹配
我們只需要從那之後開始匹配即可
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">`abc`<u>`ab`</u></span><span style="color:red">`a`</span>`bcabd`
<span style="color:green"><u>`ab`</u>`cab`</span><span style="color:red">`d`</span>
`^`
</div>
----
從第3個字元開始匹配
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">`ab`</span><span style="color:red">`c`</span>`abd`
`^`
</div>
再次匹配失敗，把字串移動到必要的匹配上
----
從第1個字元開始匹配
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
## 次長相同前綴後綴
可以知道最長相同前綴後綴是字串自己本身
而我們要求的是次長，以 `abcabd` 為例
| 字串 | 次長相同前綴後綴 |
| --- | ------------- |
|`a` | $\phi$
|`ab` | $\phi$
|`abc` | $\phi$
|<u>`a`</u>`bc`<u>`a`</u> | `a`
|<u>`ab`</u>`c`<u>`ab`</u> | `ab`
|`abcabd` | $\phi$
----
## failure function
則當匹配失敗時，取其次長相同前綴後綴，
則可以直接移動詢問字串 `W` 到還未匹配過的位置
```python
while 還沒比對到最後一個字元:
if 比對字元成功:
比對下一個字元
else if 比對字元失敗:
取其次長相同前綴後綴，移動字串 W
else if 成功匹配整個字串:
紀錄答案，並且取其次長相同前綴後綴，移動字串 W
```
----
為了實作方便，
會將儲存次長相同前綴後綴最後一個字元的 index (0-base)
| 字串 | 次長相同前綴後綴index |
| --- | ------------- |
|`a` | $-1$
|`ab` | $-1$
|`abc` | $-1$
|<u>`a`</u>`bc`<u>`a`</u> | $0$
|<u>`ab`</u>`c`<u>`ab`</u> | $1$
|`abcabd` | $-1$
如果為空字串則為 `-1`，第一個 index 為 `0`，所以設前一個 `0-1 = -1`
----
## 程式碼
```cpp=
int failure[MXN]; //儲存以第i個為結尾的次長相同前綴後綴
void KMP(string s, string w){
// i 為字串 s 當前 index, j 為字串 w 以匹配到的 index
for(int i = 0,j = -1; i < s.size(); ++i){
while(j >= 0 && s[i] != w[j+1]){ // 當匹配失敗找到次長相同前綴後綴，移動字串W
j = failure[j];
}
if(s[i] == w[j+1]){ // 當字元相等
++j;
}
if(j+1 == w.size()){ // 當字串完全匹配
ans.push_back(i-w.size()+1); // 加進答案
j = failure[j]; // 移動字串W
}}}
```
----
## build
建 次長相同前綴後綴表
當一個字串想要加長 次長相同前綴後綴
則需在最尾端加上一個跟前綴下一個字元相同的字元
如果下一個相同代表可以加長，否則需要回到當前的次長相同前綴後綴
<u>ab</u>cc<u>ab</u> $\to$ <u>ab<span style="color:red">c</span></u>c<u>ab<span style="color:red">c</span></u>
----
因此當我們求出前 $i$ 個字元的次長相同前綴後綴，
如果想要求 $i+1$ 的次長相同前綴後綴
則是看原本的位置指到字元能不能加長
如果相同則可以加長
否則則找次長相同前綴後綴
----
## 程式碼
```cpp=
int failure[MXN];
void build_failure(string& w){
for(int i=1,j=fauilre[0]=-1;i<w.size();i++){
while(j>=0 && w[i] != w[j+1]){ //當不相同無法匹配
j = failure[j];
}
if(w[i] == w[j+1]){ // 如果可以加長長度，則為前一個答案+1
++j;
}
failure[i] = j; // 紀錄答案
}
}
```
----
## 複雜度
### build failure table
字元兩兩比對次數最多 $2 |W|$ 次
比對成功，長度增長；比對失敗，長度減短。總共增長 $|W|$ 次、最多減短 $|W|$ 次。邊框長度最多變動 $2 |W|$ 次
### search word
字元兩兩比對次數最多 2|S| 次
原理同上
複雜度 $O(|W|+|S|)$
---
## hash
中文叫雜湊
雜湊函式(hash function) 把資料壓縮，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值。雜湊值通常用一個短的隨機字母和數字組成的字串來代表
----
### rolling hash
選一個整數 $p$ , 把字串轉換成 $p$ 進位的數字來儲存
原本字串比對是否相同需要 $O(|S|)$, 轉換成數字比較是否相同只需要 $O(1)$ 的時間
----
S = "ABCA" 為例, 轉成 $p$ 進位
則會變成 $A\cdot p^3 + B\cdot p^2 + C\cdot p^1 + A \cdot p^0$
而當字串非常長的時, 轉換會超出 long long 範圍
因此通常會進行 mod 後再儲存
----
$p$ 通常大於值域的質數降低碰撞機率 ( ex: 13331, 14341, 75577)
mod 為模數，通常選質數降低碰撞機率，選約為 $10^9$ 附近的數字避免計算過程溢位
(ex: $10^9$+7, 998244353, 999997771)
可以把一些質數放[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/primes.cpp)以被不時之需
----
### 建表
$H_{0,k}$ 為字串 $s[0,k]$ hash 出來的結果
$H_{0,k} = (s_0\cdot p^k + s_1\cdot p^{k-1} + s_2\cdot p^{k-2} ... + s_k\cdot p^0)$ % mod
$\to H_{0,0} = (s_0\cdot p^0)$ % mod
$\to H_{0,1} = (H_{0,0}\cdot p + s_1)$ % mod
$\to H_{0,2} = (H_{0,1}\cdot p + s_2)$ % mod
$\to H_{0,i} = (H_{0,i-1}\cdot p + s_i)$ % mod
----
建立所有前綴的 Hash 值 $H_{[0:k]}$
```cpp=
const ll P = 75577;
const ll MOD = 998244353;
ll Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
int val = 0;
for(int i=0; i<s.size(); i++){
val = (val * P + s[i]) % MOD;
Hash[i] = val;
}
}
```
----
### 字串子區間的 Hash 值
$Q$ 筆詢問，每次問字串 $s$ 中有沒有某個子字串為 $x$
假設要求字串 $s$ 區間 $[l,r]$ 的Hash值為
$H_{l,r} = (s_l * p^{r-l+1} + s_{l+1} * p^{r-l} + s_{l+2} * p^1 + ... +s_r * p^0)$ % mod
$\to (H_r - H_{l-1} * p^{r-l+1})$
----
以區間[1,3]為例
<div style="font-size: 30px">
$H_{0,3} = (s_0 * p^3 + s_1 * p^2 + s_2 * p^1 + s_3 * p^0)$ % mod
$H_{0,0} = (s_0 * p^0)$ % mod
$H_{0,3} - H_{0,0} * p^3$
$=(s_0 * p^3 + s_1 * p^2 + s_2 * p^1 + s_3 * p^0)-(s_0 * p^3)$ % mod
$=(s_1 * p^2 + s_2 * p^1 + s_3 * p^0)$ % mod
$=H_{1,3}$
</div>
----
前面 $O(N)$ 建好前綴 Hash 表
即可 $O(1)$ 時間計算所有子字串的 Hash 值
而如果題目需要不斷詢問 字串中兩個不同的子區間是否為相同字串時，即可 $O(1)$ 判斷
----
## double hashing
在某些題目測資特別設計之下, 可能發生碰撞
在這種情況下，我們會再多選一個 $p_2$ 或者 $mod_2$ 重新建立新的 Hash 值
使得每個區間都有兩個 Hash 值
----
```cpp=
const ll P1 = 75577;
const ll P2 = 12721; // 多一個質數 p2
const ll MOD = 998244353;
pair<ll,ll> Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
pair<ll,ll> val = make_pair(0,0);
for(int i=0; i<s.size(); i++){
val.first = (val.first * P1 + s[i]) % MOD;
val.second = (val.second * P2 + s[i]) % MOD;
Hash[i] = val;
}
}
```
----
## Longest Palindromic Substring
給定一個字串 $s (1 \le |s| \le 10^5)$，求所有的回文子字串中，長度最長為多少
"ababa" $\to$ 5
"caaabc" $\to$ 3
----
## brute force
暴力窮舉所有區間 $O(N^2)$
再花 $O(N)$ 時間檢查窮舉的區間是否為回文
複雜度 $O(N^3)$
----
## brute force with hash
hash 後可以花 O(1) 時間知道字串某個子區間的hash值
如果一個字串是回文，則字串本身與反過來會相同
先預處理
字串 $s$ 的 hash 值以及
反轉的字串 reverse($s$) 的 hash 值
則可以花 $O(1)$ 時間判斷字串是否為回文
複雜度 $O(N^3) \to O(N^2)$
----
但還可以更快
如果一個字串是回文，
把最左以及最右的字元刪掉也是回文
或者最左最右分別加上相同字元也是回文
s="abaaba"
同時刪除最左右 $\to$ "baab"
同時加上字元'c' $\to$ "cabaabac"
----
因此具有單調性可以使用二分搜!
二分搜尋最長回文半徑 $r$，
每次判斷以每個字元為中心且半徑為 $r$ 的字串是否為回文
如果是回文，則代表此字串最長回文半徑至少為 $r$
不是回文則代表此字串最長回文半徑小於 $r$
檢查是否為回文可以用 hash $O(1)$ 判斷
----
而回文也分為兩種，長度為奇數或偶數
若為奇數，中心點為字元 "abcba"
若為偶數，中心點為空白 "abba"
所以檢查時兩種情況(中心為字元或空白)都要檢查
----
## 複雜度
對於每個位置當成中心點, 二分搜最長回文長度
每個字元或空白為中心且半徑為 $r$ 的字串是否為回文
總共 $O(N)$ 個位置 二分搜 $O(\log N)$
複雜度 $O(N\log N)$
----
有些字串的題目都具有單調性使之可以二分搜尋
再搭配 hash，通常都可以做到 $O(N\log N)$ 的複雜度
----
## [Hash + 修改](https://cses.fi/problemset/task/2420)
給定一個字串, 兩種操作
1. 詢問區間 [l, r] 是否為回文
2. 修改第 $i$ 個字元
多了第二種操作 修改字元
----
可以發現我們 Hash[i] 儲存的是前綴 Hash 值
修改第 $i$ 個字元會影響到 Hash[i:n]
也就是從第 $i$ 個位置的 Hash 值到最後一個的 Hash 值
----
而原本 hash 的建法
Hash[2] = $p^2\cdot s[0] + p^1\cdot s[1] + p^0\cdot s[2]$
Hash[3] = $p^3\cdot s[0] + p^2\cdot s[1] + p^1\cdot s[2] + p^0\cdot s[3]$
會發現修改位置 2 則, 後面每格的 hash 值對於 s[2] 乘的 $p$ 冪次會不同
----
因此我們通常會把 $p$ 的冪次反過來建表
Hash[2] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2]$
Hash[3] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2] + p^3\cdot s[3]$
如此一來修改某個元素時, 對於所有 Hash[$i:n$] s[i] 乘上的冪次都會相同不影響
----
區間修改從 $i$ 開始到結尾的
因此我們可以使用 BIT 等資料結構來維護區間加值
使用 BIT 記得要 1-base, 可以在字串前面加上一個填充字元
----
從修改的位置 pos 加值, 加的值 為新字元與舊字元的差值 $\times p$ 的 pos 次方
所有 $p$ 的次方可以在一開始先 $O(N)$ 預處理
由於要求回文, 因此要儲存正反字串分別的 Hash 值
```cpp
void update(int pos, int ch){
BIT.update(pos, (ch - s[pos]) * p[pos] % MOD);
revBIT.update(n-1-pos, (ch-s[pos]) * p[n-pos-1] % MOD);
}
```
----
### 總複雜度
修改 $O(\log N)$
詢問 $O(1)$
---
### 2023 海洋盃
熱身賽算一次加分
正式賽算一次模擬賽成績
報名連結： https://forms.gle/UEVqGczed4VPjach9
粉絲專頁： https://www.facebook.com/OceanCupProgrammingContest
----
### Homework and Practice
deadline: 5/6
link: https://vjudge.net/contest/555030
Google Drive
Gist
Clipboard
Sign in with Wallet
