# 字串 Author: guagua0407 --- - Hashing - KMP - Z - Trie --- ## Hashing ---- 比對字串是 $O(n)$ 太慢了！ ---- ### 定義 維基百科：**雜湊函數**(Hash function)，是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函數把訊息或資料壓縮成摘要，使得資料量變小，將資料的格式固定下來。該函數將資料打亂混合，重新建立一個叫做雜湊值。 ----  ---- ### 性質 - 不可逆 - $f(A) \neq f(B) \implies A \neq B$ - 有可能會**碰撞** ---- ### 碰撞 - $(A \neq B) \land (f(A) = f(B))$ - 燒雞 - 目標是把碰撞機率降低 ---- ### Rolling Hash $\sum_{i=0}^{n-1} (S[i] * x^{n-i-1}) \pmod{M}$ $x,M$ 要自己決定好 ---- ### 例子 假設 a-z 分別對應 1-26 則 banana 的 Hash Value 是 $2x^5+x^4+14x^3+x^2+14x^1+1 \pmod{M}$ ---- 這個公式有一個最重要的性質： $f(A+B)=f(A)x^{|B|}+f(B)$ ---- 移向後變成 $f(B)=f(A+B)-f(A)x^{|B|}$ ---- 可以發現我們只要把所有前綴的 Hash Value 都記起來 就可以 O(1) 查詢任意子字串的 Hash Value 了！ ---- 可以把 Rolling Hash 想像成一個三角形  ---- 兩個子字串合併之後就會變成這樣  ---- $x$ 和 $M$ 的值要取多少？ 可以發現 $x$ 只要大於你要 hash 的字元的種類就好，所以假設你是要 hash 英文字母可以取個 29 之類的，不過通常其實隨機就好了。 $M$ 就是選一個大小合適的質數$(1e9+7,2^{61}-1)$，~~或是你直接讓他 overflow~~ ---- 重點來了，$M$ 的大小代表你 Hash 完之後總共會有幾種值，也就直接影響了碰撞的機率。 那機率怎麼算呢？ ---- ### [Birthday Paradox](https://en.wikipedia.org/wiki/Birthday_problem) $N$ 個人中有兩人生日同天機率是多少？ ---- 把生日換成 Hash Value 可以發現大概需要 $O(n^2)$ 級別的 $M$ 才能保證兩兩不相同。 所以看到 $10^5$ 級別以上的 $N$ 就得開砸 int_128 或做超多個 hash？ ---- 現在給你這個問題：在長度為 $10^6$ 的 $T$ 裡找有沒有子字串等於長度為 $10^5$ 的 $S$ 會發現在 $10^6$ 級別的 hash 中不需要滿足兩兩不同，他們只是要和 $S$ 比較而已。 ---- 所以其實重要的是實際上會用到的比較次數，在上面那題中比較次數只為 $10^6$ 級別，所以 $10^9$ 級別的 $M$ 就足夠了。 所以不要一興奮就開砸了，太複雜的 hash 是會讓你常數破台的 ---- ### 用途 包括但不限於： - $O(n)$ 找 $A$ 中有沒有 $B$ - $O(n^2logn)$ 找有幾種子字串 - $O(nlogn)$ 找最長回文子字串 - $O(nlogn)$ 找字典序最小字串橫移 ----  ---- ### 習題 [CSES Finding Periods](https://cses.fi/problemset/task/1733/) [USACO Bovine Genetics](http://www.usaco.org/index.php?page=viewproblem2&cpid=741) [COCI Sateliti](https://evaluator.hsin.hr/tasks/HONI202135sateliti/) [BOI Genetics](https://oj.uz/problem/view/BOI18_genetics) --- ## KMP ---- ### 定義 $\pi[i]= S[0...i]$ 中最長的前綴滿足他同時也是後綴 當然， $\pi[i]$ 要小於 $i+1$ ---- ### 例子 | $S[i]$ | a | a | b | a | a | a | b | | --- | --- | --- | --- | --- | --- | --- | --- | | $\pi[i]$ | 0 | 1 | 0 | 1 | 2 | 2 | 3 | ---- 暴力？ $O(n^2)$ 還能更好！ ---- ### 觀察一 $\pi[i+1]<=\pi[i]+1$ ---- 最好情況： $(S[ \pi[i] ]=S[i+1]) \implies (\pi[i+1]=\pi[i]+1)$ ----  ---- ### 觀察二 如果 $S[\pi[i]] \neq S[i+1]$ ？ 那現在就要試一個最大的 $j<\pi[i]$ ，試得 $j$ 滿足 $S[0...j-1]$ 同時是 $S[0...i]$ 的前綴和後綴。 ----  ---- 找到 $j$ 之後，一樣看 $S[j]$ 有沒有等於 $S[i+1]$，有的話你就找到答案了，否則就在往下找一個最大滿足條件的 $k$。 一直重複上面的步驟到找到為止就好了。 ----  ---- 可以發現 $k=\pi[j-1]$！ ---- ### 總結 - 先算出 $\pi[0...i-1]$ - 令 $j=\pi[i-1]+1$ - 如果 $S[j]=S[i]$ 則 $\pi[i]=j$ ，否則讓 $j=\pi[j-1]$ - 如果 $j$ 變成 $0$ 了那 $\pi[i]=0$ ---- 時間複雜度呢？ 看起來貌似是 $O(n^2)$，但因為每移動一格 $\pi$ 值最多只會多一，所以其實只有 $O(n)$ ---- ```cpp= vector<int> pi(const string &s) { int n = (int)s.size(); vector<int> pi_s(n); for (int i = 1, j = 0; i < n; i++) { while (j > 0 && s[j] != s[i]) { j = pi_s[j - 1]; } if (s[i] == s[j]) { j++; } pi_s[i] = j; } return pi_s; } ``` ---- ### 習題 [POI Template](https://szkopul.edu.pl/problemset/problem/PT4yHRX9Mmz85ndhNPGCi_WB/site/?key=statement) --- ## Z ---- ### 定義 $z[i]= S$ 中以 $i$ 為左界最長的子字串長度使得這個子字串也是 $S$ 的前綴 ---- ### 例子 | $S[i]$ | a | a | b | a | a | a | b | | --- | --- | --- | --- | --- | --- | --- | --- | | $z[i]$ | 7 | 1 | 0 | 2 | 3 | 1 | 0 | ---- 暴力？$O(n^2)$ 還能更好！ ---- 我們可以維護一個 range $(x,y)$ 代表目前所有 $S[x...y]=S[0...y-x]$ 中 $y$ 最大的 ----  ---- 要算第 $i$ 格時，我們可以先看 $z[i-x]$ 如果 $i+z[i-x]<y$ 那 $z[i]=z[i-x]$ ---- 如果 $i+z[i-x]>=y$ 就代表說 $S[0...y-i]=S[i...y]$ 這時候就因為已經用不了前面算過的資訊了，所以就要從 $y+1$ 開始一個一個比對到不一樣為止，同時更新 $y$。 ---- 時間複雜度呢？ 因為每次比對 $y$ 都會增加 $1$，所以最多只會有 $n$ 次比對，$O(n)$！ ---- ```cpp= vector<int> z(n,0); int x=0,y=0; for(int i=0;i<n;i++){ z[i]=max(0,min(z[i-x],y-i+1)); while(i+z[i]<n and str[z[i]]==str[i+z[i]]){ x=i; y=i+z[i]; z[i]++; } } ``` ---- ### 習題 [CF Vasya and Big Integers](https://codeforces.com/contest/1051/problem/E) [CF Prefixes and Suffixes](https://codeforces.com/problemset/problem/432/D) --- ## Trie ----  ---- 每個字串都被當成一條鍊來存在樹上 ---- ### 可以幹嘛 - O(n) 插入，移除字串 - O(n) 查找字串 - O(n) 詢問有幾個前綴為 $S$ 的字串 ---- 插入 ```cpp= void insert(string str){ int v=0,i=0; while(i<str.length()){ if(trie[v][str[i]-'a']==-1){ trie[v][str[i]-'a']=cur; v=cur; c[cur]=str[i]; cur++; } else{ v=trie[v][str[i]-'a']; } i++; } cnt[v]++; } ``` ---- 詢問 ```cpp= int query(string str){ int v=0,i=0; while(i<str.length()){ v=trie[v][str[i]-'a']; i++; } return cnt[v]; } ``` ---- ### 01trie 可以把數表示成一個 01 字串（二進位） 把這些字串丟到 trie 裡就是一個 01trie ---- 可以幹嘛？ 假設數字的值域是 $X$ 那剛剛那些操作的時間複雜度就會都變成 $O(logX)$ ---- ## [例題](https://judge.yosupo.jp/problem/set_xor_min) 題目：現在有一堆數，有三個操作 - 加入一個數 $x$ - 移除一個數 $x$ - 給一個數 $x$ ，求這些數中跟 $x$ xor 完的最小值可以是多少 ---- 因為 trie 有查詢前綴的特性，所以你可以從最大的 bit 枚舉到最小的 bit。 設 $x$ 的第 $k$ 個 bit 為 a ，那就看說如果在目前的前綴中的第 k 個 bit 設成 ${(a \oplus 1)}$ 變成新的前綴，包含這個新的前綴的個數是不是為 0。 ---- 不是的話就可以成功把第 k 個 bit 設成 ${(a \oplus 1)}$。 否則就只能設成 ${a}$，並且 $ans$ 要加上 $2^k$ ---- ### 習題 [JOIOC Selling RNA Strands](https://oj.uz/problem/view/JOI16_selling_rna) [AC XOR Game](https://atcoder.jp/contests/arc122/tasks/arc122_d) --- END