Trie

字典树(Trie)

字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。

字典树可以高效处理一类字符串、异或最大值以及数集维护问题；

以下是一个Trie树模板：

# include <iostream>
# include <string>
# include <vector>

class Trie {
public:
    # define ALPHABET_SIZE 26
    # define MAX_CAPACITY 100000

    int cnt; // 维护当前结点标号，头结点标号为0
    int next[MAX_CAPACITY][ALPHABET_SIZE];
    bool isEndOfWord[MAX_CAPACITY];  // 标记某结点结尾的字符串是否存在

    void insert(std::string&s) {
        // TODO: 插入字符串s到Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) next[p][index] = ++cnt;
            p = next[p][index];
        }
        isEndOfWord[p] = true;  // 每次插入完成时在这个字符串所代表的节点处打上标记
    }

    Trie(std::vector<std::string>&words) {
        // TODO: 构建Trie树
        for(auto &word : words) insert(word);
    }
    bool find(std::string&s) {
        // TODO: 查询字符串s是否在Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) return false;
            p = next[p][index];
        }
        return isEndOfWord[p];
    }
};

注意字符串最好还是传递引用，在字符串I/O开销很大时往往会造成大量的不必要的复制，可能有内存超限的隐患；