最短前缀（字典树）------------Five-菜鸟级

                                                             最短前缀

时限：1000 MS		内存限制：30万K
提交材料共计：21820		接受： 9346

描述

字符串的前缀是从给定字符串的开头开始的子字符串。“碳”的前缀是：“c”、“ca”、“car”、“carb”、“caro”和“碳”。请注意，在此问题中，空字符串不被视为前缀，但每个非空字符串都被视为其本身的前缀。在日常语言中，我们倾向于用前缀来缩略单词。例如，“碳水化合物”通常被缩写为“carb”。在这个问题中，给定一组单词，您将为每个单词找到唯一标识它所代表的单词的最短前缀。

在下面的样本输入中，“碳水化合物”可以缩写为“碳水化合物”，但不能缩写为“碳水化合物”(或任何较短的碳水化合物)，因为列表中还有其他以“碳水化合物”开头的词。

精确匹配将覆盖前缀匹配。例如，前缀“car”与给定的单词“car”完全匹配。因此，人们毫不含糊地理解，“CAR”是“CAR”的缩写，而不是“CAR”或列表中以“CAR”开头的任何其他词的缩写。

输入

输入至少包含两行，但不超过1000行。每一行包含一个单词，由1到20个小写字母组成。

输出量

输出包含与输入相同的行数。输出的每一行包含输入的对应行中的单词，后面是一个空格，最短的前缀唯一地(没有歧义)标识这个单词。

样本输入

carbohydrate
           cart
          carburetor
          caramel
          caribou
          carbonic
          cartilage
          carbon
         carriage
         carton
         car
         carbonate

样本输出

carbohydrate carboh
           cart cart
           carburetor carbu
           caramel cara
          caribou cari
          carbonic carboni
          cartilage carti
          carbon carbon
          carriage carr
         carton carto
         car car
         carbonate carbona

题目链接： http://poj.org/problem?id=2001

 题解： 

        这是trie(字典)树模板题，字典树+前缀的东西，给节点打个标记就行 与计数一样 某个单词的字符走到只标记过一次的节点（证明字符节点只有该单词走过 可以代表该单词）就行了。想了解 字典树（点击即可）

AC 代码：

  

   

    

     

    
    

     

      #include<stdio.h> 
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #define N 2501
     
    
   

    

     

    
    

     

      int trie[N][27]; 
     
    
   

    

     

    
    

     

      int trie_flag[N]; 
     
    
   

    

     

    
    

     

      int tot=0;
     
    
   

    

     

    
    

     

      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;
     
    
   

    

     

    
    

     

      		 trie_flag[trie[root][id]]++; //给该字符节点打一个标记（计数）
     
    
   

    

     

    
    

     

      		 root=trie[root][id];
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void search(char *s){
     
    
   

    

     

    
    

     
		printf("%s ",s);
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

      	{    
     
    
   

    

     

    
    

     
	    printf("%c",s[i]);
     
    
   

    

     

    
    

     

      	     id=s[i]-'a';
     
    
   

    

     

    
    

     
		if(trie_flag[trie[root][id]]==1)break;//找到节点为 只标记过1次的
     
    
   

    

     

    
    

     

      		   root=trie[root][id];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	 printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {   char s[1005][25];int i=0,n=0; 
     
    
   

    

     

    
    

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

    

     

    
    

     
	memset(trie_flag,0,sizeof(trie_flag));
     
    
   

    

     

    
    

     
	 while(scanf("%s",&s[n])!=EOF)insert(s[n++]);//输入单词表 
     
    
   

    

     

    
    

     
     while(n--)search(s[i++]);//输出结果 
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

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

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