题目链接: 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; }