string algorithm1

範例

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

結構

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

rolling hash

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值

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