hdu 1251 统计难题（字典树）-白红宇

题目链接：

分析：

关于字典树的题目似乎都有一个普通适用性的模板，有时只是稍加改动来满足临时的要求，我的一个简单的模板

#define MAXNUM 26//定义字典树结构体typedef struct Trie{    bool flag;//从根到此是否为一个单词    Trie *next[MAXNUM];}Trie;//声明一个根Trie *root;//初始化该根void init(){    root = (Trie *)malloc(sizeof(Trie));    root->flag=false;    for(int i=0;i
     
      next[i]=NULL;}//对该字典树的插入单词操作void insert(char *word){    Trie *tem = root;    while(*word!='\0')    {        if(tem->next[*word-'a']==NULL)        {            Trie *cur = (Trie *)malloc(sizeof(Trie));            for(int i=0;i
      
       next[i]=NULL;            cur->flag=false;            tem->next[*word-'a']=cur;        }        tem = tem->next[*word-'a'];        word++;    }    tem->flag=true;}//查询一个单词的操作bool search(char *word){    Trie *tem = root;    for(int i=0;word[i]!='\0';i++)    {        if(tem==NULL||tem->next[word[i]-'a']==NULL)        return false;        tem=tem->next[word[i]-'a'];    }    return tem->flag;} //释放字典树内存操作，由于本题测试数据后程序自动跳出，所以这里没写释放内存函数 void del(Trie *cur) {
        for(int i=0;i
       
        next[i]!=NULL)         del(cur->next[i]);     }     free(cur); }

这道题目是一道典型的字典树题目（Trie）,题目解法类似于的解法，这里搜索前缀，然后对后边用一个递归搜索就可以求出有多少字符串是以此字符串为前缀，注意本身也是自己的前缀。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAXNUM 26using namespace std;//单词char words[50005][12];//定义字典树typedef struct Trie{    bool flag;//从根到此是否为一个单词    Trie *next[MAXNUM];}Trie;Trie *root;int count_num;void init(){    root = (Trie *)malloc(sizeof(Trie));    root->flag=false;    for(int i=0;i
         
          next[i]=NULL;}void insert(char *word){    Trie *tem = root;    while(*word!='\0')    {        if(tem->next[*word-'a']==NULL)        {            Trie *cur = (Trie *)malloc(sizeof(Trie));            for(int i=0;i
          
           next[i]=NULL; cur->flag=false; tem->next[*word-'a']=cur; } tem = tem->next[*word-'a']; word++; } tem->flag=true;}void dfs(Trie *cur){ if(cur->flag)count_num++; for(int i=0;i
           
            next[i]!=NULL) dfs(cur->next[i]); }}int search(char *word){ Trie *tem = root; count_num = 0; for(int i=0;word[i]!='\0';i++) { if(tem==NULL||tem->next[word[i]-'a']==NULL) return 0; tem=tem->next[word[i]-'a']; } dfs(tem); return 1;}int main(){ init(); int t=0; char w[12]; while(gets(w)) { if(*w=='\0')break; insert(w); t++; } while(scanf("%s",w)!=EOF) { search(w); printf("%d\n",count_num); } return 0;}

http://www.cnblogs.com/newpanderking/archive/2012/11/02/2751665.html