Trie字典树

Trie树是一种树形数据结构，又称字典树。用来存放大量的字符串。借助于它们的公共前缀来减少存储空间和访问时间，效率很高。

不同于一般的树形结构，Trie的数据是存放在边中而不是存放在点中，这样可以更快的访问字符串下一个字符，利用下一个字符的数据内容来作为访问的下标。
例如，再上图中，Trie[0]['a'] = 1,Trie[0]['b'] = 2,Trie[1]['h'] = 12;当想要知道有没有以c开头的单词时，只需访问下Trie[0]['c']是否为0即可。
模板

//存储形式
int Trie[maxn][26];
int sum[maxn][26];
int tot = 0;
/*Trie[][]的值为第几个结点，而数据是存放在边上的，sum用来标记其他的信息，比如有多少个字符串经过这个点，以该点位结尾的字符串有多少个等。*/

插入(insert) 插入代码可以说是Trie树的核心！务必理解透彻。

void insert(char *s){
    int root = 0;
    for (int i=1;i<=len;i++){
        if (Trie[root][s[i]]==0){
            Trie[root][s[i]] = ++tot;
        }
        root = Trie[root][s[i]];
    }
    return;
}

查询(query) 查询可以根据需求来查找自己需要的东西，前缀，包含该前缀的字符串个数等

int query(char *s){
    int root = 0;
    int ans = 0;
    for (int i=1;i<=len;i++){
        if (Trie[root][s[i]]==0)
            return 0;
        Func_ans();  //有关操作
        root = Trie[root][s[i]];
    }
    return ans;
}