<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> ```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 解 ---- ## 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(lg 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){ 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> ---- ```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; } } ``` ---- ### 字串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值 ---- ```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; } } ``` --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/460720) <div style="font-size: 30px"> 提交期限兩星期，下下星期一 18:30 截止 </div>