changed 4 years ago  
Linked with GitHub

string algorithm1

Competitive programming 2

2021/10/04

  • trie
  • bitwise trie
  • hash

trie

字典樹 ( or 字首樹 )

範例

Zerojudge d518

結構

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












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

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

\(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











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值

\(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]為例

\(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}\)

因此我們可以 \(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

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

Select a repo