字典树模板

1.用字典树实现
空间超额（MLE）的代码，还有更好更紧凑的字典树实现方法

#include<bits/stdc++.h>
using namespace std;
struct Trie{                                //字典树的定义 
    Trie* next[26];
    int num;                                //以当前字符串为前缀的单词的数量 
    Trie(){                                    //构建函数 
        for(int i=0;i<26;i++)    next[i]=NULL;
        num=0;
    }
};
Trie root;
void Insert(char str[]){                    //将字符插入字典树中 
    Trie *p=&root;
    for(int i=0;str[i];i++){                //遍历每一个字符 
        if(p->next[str[i]-'a']==NULL)        //如果该字符没有对应的结点 
            p->next[str[i]-'a']=new Trie;    //创建一个
        p=p->next[str[i]-'a'];
        p->num++;                            //（保证输入的每个单词都不一样） 
    }
}
int Find(char str[]){                        //返回以字符串为前缀的单词的数量 
    Trie* p=&root;
    for(int i=0;str[i];i++){                //在字典树中找到该单词的结尾位置 
        if(p->next[str[i]-'a']==NULL)
            return 0;
        p=p->next[str[i]-'a'];
    }
    return p->num;
} 
int main(){
    char str[11];
    while(gets(str)){
        if(!strlen(str))    break;            //输入了一个空行
        Insert(str);
    }
    while(gets(str))    cout<<Find(str)<<endl;
    return 0;
}

2.用map实现
这一题用map来做非常简单，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    char str[10];
    map<string,int>m;
    while(gets(str)){
        int len=strlen(str);
        if(!len)    break;
        for(int i=len;i>0;i--){
            str[i]='\0';
            m[str]++;
        }
    }
    while(gets(str))    cout<<m[str]<<endl;
    return 0;
}