最短前缀（字典树)

---

最短前缀

时限：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;    
}

---