<style> .reveal .slides { text-align: left; font-size:30px; } </style> # String Algorithm Introduction to Competitive Programming 2022/04/13 ---- * 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 解 將數字轉成二進位後存成 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 值 而如果題目需要不斷詢問 字串中兩個不同的子區間是否為相同字串時，即可 O(1) 判斷 ---- ## 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; } } ``` ---- ## 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" 所以檢查時兩種情況(中心為字元或空白)都要檢查 ---- ## 複雜度 二分搜，每次花 O(N) 時間檢查 每個字元或空白為中心且半徑為 $r$ 的字串是否為回文 複雜度 $O(NlgN)$ ---- 有些字串的題目都具有單調性使之可以二分搜尋 再搭配 hash，通常都可以做到 $O(NlgN)$ 的複雜度 --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/489161) <div style="font-size: 30px"> 提交期限兩星期，4/27 23:59 截止 </div>