字典树模板

模板题
AC代码 : //注意要用C++交,G++会MLE. （100ms左右）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

typedef struct trie
{
    int cnt;     //统计每个单词前缀出现的次数（也包括统计每个单词出现的次数）
    struct trie *next[26];
}Trie;

Trie *creatTrieNode()  //初始化节点.
{
    Trie *node = (Trie *)malloc(sizeof(Trie));
    node->cnt=0;
    memset(node->next, 0, sizeof(node->next));   //初始化为空指针.
    return node;
}

void Trie_Insert(Trie *root , char *word)
{
    Trie *node = root;
    char *p = word;
    int id;
    while(*p != '\0' )   //只有读到字符串末尾才会停止读入,即读到'\0'出.
    {
        id = *p - 'a';
        if(node->next[id] == NULL){
            node->next[id] = creatTrieNode();
        }
        node = node->next[id];
        ++p;
        node->cnt += 1 ;    //这行代码用于统计每个单词前缀出现的次数（也包括统计每个单词出现的次数）
    }
}

int Trie_Search(Trie *root , char *word)
{
    Trie *node = root;
    char *p = word ;
    int id;
    while( *p != '\0')
    {
        id = *p - 'a';
        node = node->next[id];
        ++p;
        if(node == NULL)
            return 0;
    }
    return node->cnt;
}
int main()
{
    Trie *root =  creatTrieNode();// 初始化字典树的根节点
    char str[15];
    int flag=0;
    while(gets(str)){
        if(flag)
            printf("%d\n",Trie_Search(root,str));
        else{
            if(strlen(str) != 0)
                Trie_Insert(root,str);
            else
                flag=1;
        }
    }
}

对于这道题,由于数据问题,也可以用map水过.（800ms左右）
代码如下:

#include<cstdio>
#include<map>
using namespace std;
map<string,int>mp;
int main()
{
    char s[15];
    while(gets(s)){
        if(strlen(s) == 0)
            break;
        for(int i=strlen(s);i>0;i--){
            s[i] = '\0';  //把最后一个字符替换成结束符号.
            mp[s]++;
        }
    }
    while(gets(s)){
        printf("%d\n",mp[s]);
    }
}