题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1251

 题解： 这是trie(字典)树模板题，字典树+前缀的东西，坑点，没告诉你有多少单词 数组开小了 会崩

 想了解 字典树（点击即可）

  

   

    

     

    
    

     

      #include<stdio.h> 
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #define N 400001
     
    
   

    

     

    
    

     

      int trie[N][27]; 
     
    
   

    

     

    
    

     

      int sum[N]; //存从根节点到单词（前缀）的单词数
     
    
   

    

     

    
    

     

      int tot=0; //给父节点到子节点编号 区分 hash shands 
     
    
   

    

     

    
    

     

      void insert(char *s){//插入单词
     
    
   

    

     

    
    

     
	int i,id,len,root=0; len=strlen(s);
     
    
   

    

     

    
    

     
	for(i=0;i<len;i++)
     
    
   

    

     

    
    

     

      	{    id=s[i]-'a';
     
    
   

    

     

    
    

     
		if(!trie[root][id])trie[root][id]=++tot;
     
    
   

    

     

    
    

     

      		 root=trie[root][id]; sum[root]++;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      int search(char *s){//查询单词
     
    
   

    

     

    
    

     
	int i,len,id,root=0;len=strlen(s);
     
    
   

    

     

    
    

     
	for(i=0;i<len;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      	     id=s[i]-'a';
     
    
   

    

     

    
    

     
		if(!trie[root][id])return 0;
     
    
   

    

     

    
    

     

      		   root=trie[root][id];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return sum[root];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {   char s[12];
     
    
   

    

     

    
    

     
	memset(trie,0,sizeof(trie));
     
    
   

    

     

    
    

     
	memset(sum,0,sizeof(sum));
     
    
   

    

     

    
    

     
	         while(gets(s)&&strlen(s)>0)insert(s);//输入单词表 
     
    
   

    

     

    
    

     
        	 while(scanf("%s",&s)!=EOF)printf("%d\n",search(s));//输入前缀以及输出结果 
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/82959234