---
tags: Training
---

<style>
.reveal .slides {
text-align: left;
}
</style>

# string algorithm1

Competitive programming 2

2021/10/04

----

* trie
* bitwise trie
* hash

---

## trie

[字典樹](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d) ( or 字首樹 )

----


----

### 範例

[Zerojudge d518](https://zerojudge.tw/ShowProblem?problemid=d518)

----

### 結構

<div style="font-size: 30px">

每個節點有往下的指標
以及紀錄多少個字串以此為結尾

</div>

struct trie{
    trie *nxt[26];
    int cnt;    //紀錄有多少個字串以此節點結尾
    int sz;     //有多少字串的前綴包括此節點
    trie():cnt(0),sz(0){
        memset(nxt,0,sizeof(nxt));
    }
};

//創建新的字典樹
trie *root = new trie();

----

### 插入
將字串 $s$ 加入字典樹

// 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++;
}

----

### 查詢

// 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 解

----

## bitwise trie


----

### 結構

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(lg x)

void insert(int x){
    trie *now = root;  // 每次從根結點出發
    for(int i=30;i>=0;i--)
        now->sz++;
        if(now->nxt[x>>i&1] == NULL){
            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)$ 筆詢問，每次給你兩個數字 $x, d$
有多少個數字 xor $x$ 後 $\le d$

----

詢問多少個數字 xor $4$ 之後小於等於 $5$

----


----


----


----


---

## hash

中文叫雜湊

雜湊函式(hash function) 把資料壓縮，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值。雜湊值通常用一個短的隨機字母和數字組成的字串來代表

----

### rolling hash

<div style="font-size: 35px">

$H_{0,k}$ 為字串 $s[0,k]$ hash 出來的結果
其中 $p$ 為一個常數(通常選質數降低碰撞機率)
mod 為一個模數(通常選質數降低碰撞機率，通常選約為 $10^9$ 附近的數字)
</div>

<div style="font-size: 30px">

$H_{0,k} = (s_0 * p^k + s_1 * p^{k-1} + s_2 * p^{k-2} ... + s_k * p^0)$ % mod
$\to H_{0,0} = (s_0 * p^0)$ % mod
$\to H_{0,1} = (H_{0,0} * p + s_1)$ % mod
$\to H_{0,2} = (H_{0,1} * p + s_2)$ % mod
$\to H_{0,i} = (H_{0,i-1} * p + s_i)$ % mod

</div>

----

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;
    }
}

----

### 字串s區間的Hash值

<div style="font-size: 30px">

$Q$ 筆詢問，每次問字串$s$中有沒有某個子字串為$x$

假設要求字串 $s$ 區間[l,r]的Hash值為

</div>

<div style="font-size: 30px">

$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})$

</div>

----

以區間[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 值

----

## double hashing

但是還是有可能發生碰撞

在這種情況下，我們會再多選一個 $p_2$ 或者 $mod_2$
使得每個區間都有兩個Hash值

----

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;
    }
}

---

### Question Time and Practice

[Homework Link](https://vjudge.net/contest/460720)

<div style="font-size: 30px">

提交期限兩星期，下下星期一 18:30 截止

</div>