【筆記】字典樹 Trie

  • 【用途】:給定多個字串,接著多次詢問某字串有沒有出現過。
  • 【變化】01字典樹:每一層代表一個bit 或 true/false,用於查找是否出現過。
  • 【練習】HDU 4852 Xor Sum【題解
  • 【練習】Codeforces I. Interactive Casino
  • 【練習】Google Code Jam 2019 Round 1A C Alien Rhyme題解
  • 關於字串的一些名詞:字串 string s;
    • 字串長度:s.size(); 或 strlen(s);
    • 子字串 (substring):字串 s 中一段連續的字串。
    • 子序列 (subsequence):字串 s 中一段可不連續的字串,但出現順序必須和原字串相同。
    • 前綴(prefix):從頭開始的一段substring。
    • 後綴(suffix):到結尾的一段substring。

【字典樹實作】

struct TrieNode {
    int nxt[26]; //遇到a~z時的節點編號(idx)
    int cnt; //以此結尾的字串個數
} node[1000005];

int idx = 2; //root = 1

【加入一個字串】

voide insert(string s){
     int cur = 1; //從root開始
     for(auto i:s) {
          if(node[cur].nxt[i-’a’] == 0){
               node[cur].nxt[i-’a’] = idx; \\開一個新的node
               cur = idx;
               idx++;
           }
           else {
                cur = node[cur].nxt[i-’a’];
           }
     }
     node[cur].cnt++;
}

【查詢一個字串】

int query(string s){
     int cur = 1;
     for(auto i:s) {
          if(node[cur].nxt[i-’a’] == 0){
               return 0;
           }
           else {
                cur = node[cur].nxt[i-’a’];
           }
     }
     return node[cur].cnt;
}
分享本文 Share with friends