hihocoder 1024:Trie樹

題目連結：http://hihocoder.com/problemset/problem/1014

對于

trie

樹，要找出具有确定字首的所有比對的個數，這個任務可以從兩個方面來考慮。

第一方面

找出具有确定字首的所有字元串比對是

trie

樹的功能之一：通過自上而下，由根節點不斷找到下一字元對應的子節點，周遊可以得到字首串的最深節點，即末尾字元對應的節點。從目前結點出發，DFS深度優先搜尋所有孩子，一旦有節點滿足為字元串節點（字元串位設定為true），即目前節點代表的串是一個完整的串，就加入傳回字元串集合中。這樣不斷深搜所有節點，這樣就能得到所有滿足條件的字元串集合了。

第二方面

1. 由于這裡不需要得到所有具有相應字首比對的字元串的具體值，而是要得到所有具有字首的字元串的數目，是以這應該是一個計數問題，而不是一個得到所有解的問題。
2. 由于周遊字典樹的過程是自上而下的，上一個節點之能移動到下一個節點，而下一個節點不能到達上一個節點。是以對于這個資料結構，我們隻能記錄之前的狀态，對于後面的狀态的統計我們是不知情的。
3. 為了達到統計所有具有相應字首的字元串的數目，我們在每一個節點上設定一個計數器，計數器初始化為0，表示字首為該節點對應字元串的字元串的數目，這樣每次插入周遊時，如果經過該節點則待插入字元串一定具有該節點的字首比對，是以計數器+1。
4. 這樣經過插入的字典樹，每個結點的計數器的值都代表能與該節點字首比對的字元串的數目

源代碼

#include<map>
#include<iostream>
using namespace std;

/**
	字典樹節點
**/
class TrieNode{
public:
    int prefixN = 0;
    map<char, TrieNode*> children;
};

/**
	字典樹
**/
class Trie{
public:
    TrieNode* root = new TrieNode();

    int countParent(string str){
        TrieNode* now = root;

        for(int i = 0; i < str.size(); i++){
            if(now->children.count(str[i]) == 0){
                return 0;
            }
            now = now->children[str[i]];
        }

        return now->prefixN;
    }

    void insert(string str){
        TrieNode* now = root;

        for(int i = 0; i < str.size(); i++){
            if(now->children.count(str[i]) == 0){
                now->children[str[i]] = new TrieNode();
            }
            now = now->children[str[i]];
            (now->prefixN)++;
        }
    }
};

int main(){
    int num;
    string tmp;
    Trie trie;

	// 字元串插入到字典樹
    cin >> num;
    while(num--){
        cin >> tmp;
        trie.insert(tmp);
    }

	// 從字典樹中查找對應比對樹
    cin >> num;
    while(num--){
        cin >> tmp;
        cout << trie.countParent(tmp) << endl;
    }

    return 0;
}
           

Think More

1. 計數器初始化為0還是1呢
2. 插入計數器自增時需要判斷目前節點是字元串節點嗎