hdu 1251 统计难题 (字典树)

题目大意: 给出单词的词典，然后有限次询问

每次询问给出的字符在词典中作为前缀的次数

解题思路: 建立词典的字典树

用w标记此结点在建树过程中访问的次数，每经过一次就+1

查询时把查询的字符遍历字典树，遍历最后结点的w值既是答案

代码:

#include <stdio.h>  
#include <string.h>  
#include <string.h>  
#define MAX 1000000  
struct snode{  
    char ch1;  
    int next;   //第二种写法  
}Tree[MAX];  
char ch[20];  
int pd,Index,num[MAX],pre[MAX];  
  
void Add_edge(int Star,char ch2)   //建立有向图  
{  
    Tree[Index].ch1=ch2,Tree[Index].next=pre[Star];  
    num[Index]++;  
    pre[Star]=Index++;  
}  
  
void DFS(int Star,int len,int Tlen)  //DFS插入结点  
{  
    int i;  
    if(len>Tlen)  
        return ;  
    for(i=pre[Star];i!=-1;i=Tree[i].next)  
    {  
        if(Tree[i].ch1==ch[len-1])  
        {  
            num[i]++;  
            if(len<Tlen)  
            {  
                DFS(i,len+1,Tlen);  
            }  
            return ;  
        }  
    }  
    Add_edge(Star,ch[len-1]);  
    DFS(Index-1,len+1,Tlen);  
}  
  
void DFS2(int Star,int len,int Tlen)   //DFS查询w值  
{  
    int i;  
    if(len>Tlen)  
        return ;  
    for(i=pre[Star];i!=-1;i=Tree[i].next)  
    {  
        if(Tree[i].ch1==ch[len-1])  
        {  
            if(len==Tlen)  
            {  
                pd=num[i];  //num[ ]是w值  
                return ;  
            }  
            if(len<Tlen)  
            {  
                DFS2(i,len+1,Tlen);  
            }  
            return ;  
        }  
    }  
      
}  
  
int main()  
{  
    int n=0,i;  
    Index=1;  
    memset(num,0,sizeof(num));  
    memset(pre,-1,sizeof(pre));  
    memset(Tree,0,sizeof(Tree));  
    Tree[0].ch1='\0';  
    Tree[0].next=-1;  
    while(gets(ch))    //输入词典  
    {  
        if(ch[0]=='\0')  
            break;  
        DFS(0,1,strlen(ch));  
    }  
    while(gets(ch))    //查询  
    {  
        pd=0;  
        DFS2(0,1,strlen(ch));  
        printf("%d\n",pd);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,