POJ 2001 -- Shortest Prefixes

2001 -- Shortest Prefixes

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", "car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate" is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".

An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car" , not for "carriage" or any of the other words in the list that begins with "car".

Input

The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

Output

The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.

Sample Input

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

Sample Output

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://blog.csdn.net/lsjseu/article/details/8852440

trie建树，设置一个变量num，计算每个单词出现的次数。查找的时候如果num = 1则说明这是第一次出现过的单词，直接返回。

              在建tire的时候，设置一个num变量记录孩子节点的个数，如果孩子节点为1表示是一个单词节点，如果num>1表示是一个中间节点，继续搜索。

采用采用链表的方式建Trie树

1. char str[1005][25];  
2.   
3. struct Trinode{  
4.     int num;//记录孩子节点的个数  
5.     Trinode *link[26];  
6.     Trinode(int _num=0):num(_num)  
7.     {  
8.         for(int i=0;i<26;i++){  
9.             link[i] = NULL;  
10.         }  
11.     }  
12. };  
13.   
14. class Trie{  
15. public:  
16.     Trie()  
17.     {  
18.         root = new Trinode(0);    
19.     }  
20.     void insert(char *tar)  
21.     {  
22.         char ch;  
23.         Trinode *ptr = root;  
24.         while(*tar){  
25.             ch = *tar-'a';  
26.             if(ptr->link[ch]==NULL){  
27.                 ptr->link[ch] = new Trinode(1);//单词节点的num为1  
28.             }  
29.             else  
30.                 ptr->link[ch]->num++;           
31.             ptr = ptr->link[ch];  
32.             tar++;  
33.         }  
34.     }  
35.   
36.     void seach(char *tar)  
37.     {  
38.          int i = 0;  
39.          char ch;  
40.          Trinode* ptr = root;  
41.          while(ch = *tar){  
42.              cout<<ch;  
43.              if(ptr->link[ch-'a']->num == 1)return;  
44.              ptr = ptr->link[ch-'a'];  
45.              tar++;  
46.          }  
47.     }   
48. private:  
49.     Trinode *root;  
50. };  
51.   
52.   
53. class ShortestPrefixes{  
54. public:  
55.     void solution()  
56.     {  
57.         int n,i;  
58.         Trie tree;  
59.         while(scanf("%s",str[n])!=EOF)  
60.         //cin>>n;  
61.         //for(int i=0;i<n;i++)  
62.         {  
63.             //scanf("%s",str[i]);  
64.             tree.insert(str[n]);  
65.             n++;  
66.         }  
67.         for(i=0;i<n;++i)  
68.         {  
69.             printf("%s ",str[i]);  
70.             tree.seach(str[i]);  
71.             printf("\n");  
72.         }  
73.     }  
74. }; 

http://blog.csdn.net/cathaypoplar/article/details/18520757

1. public class Main {  
2.   
3.     public static void main(String[] args) {  
4.         Scanner scn = new Scanner(System.in);  
5.         Trie trie = new Trie();  
6.         Queue<String> queue = new LinkedList<String>();  
7.         while (scn.hasNext()) {  
8.             String word = scn.nextLine();  
9.             queue.offer(word);  
10.             trie.insert(word);  
11.         }  
12.         while (!queue.isEmpty()) {  
13.             String word = queue.poll();  
14.             System.out.println(word + " " + trie.search(word));  
15.         }  
16.         scn.close();  
17.     }  
18.   
19. }  
20.   
21. class Trie {  
22.   
23.     private Node root;  
24.   
25.     public Trie() {  
26.         root = new Node(new Node[26], 0);  
27.     }  
28.   
29.     public void insert(String word) {  
30.         Node current = root;  
31.         for (int i = 0; i < word.length(); ++i) {  
32.             if (null != current.getChildrenItem(word.charAt(i) - 'a')) {  
33.                 current = current.getChildrenItem(word.charAt(i) - 'a');  
34.                 current.setCount(current.getCount() + 1);  
35.             } else {  
36.                 Node newNode = new Node(new Node[26], 1);  
37.                 current.setChildrenItem(word.charAt(i) - 'a', newNode);  
38.                 current = newNode;  
39.             }  
40.         }  
41.     }  
42.   
43.     public String search(String word) {  
44.         Node current = root;  
45.         StringBuilder prefix = new StringBuilder();  
46.         for (int i = 0; i < word.length(); ++i) {  
47.             if (1 == current.getCount()) {  
48.                 break;  
49.             }  
50.             prefix.append(word.charAt(i));  
51.             current = current.getChildrenItem(word.charAt(i) - 'a');  
52.         }  
53.         if (1 == current.getCount()) {  
54.             return prefix.toString();  
55.         } else {  
56.             return word;  
57.         }  
58.     }  
59.   
60. }  
61.   
62. class Node {  
63.   
64.     private Node[] children;  
65.     private int count;  
66.   
67.     public Node(Node[] children, int count) {  
68.         this.children = children;  
69.         this.count = count;  
70.     }  
71.   
72.     public Node getChildrenItem(int i) {  
73.         return children[i];  
74.     }  
75.   
76.     public void setChildrenItem(int i, Node node) {  
77.         children[i] = node;  
78.     }  
79.   
80.     public int getCount() {  
81.         return count;  
82.     }  
83.   
84.     public void setCount(int count) {  
85.         this.count = count;  
86.     }  
87.   
88. } 

http://www.acmerblog.com/POJ-2001-Shortest-Prefixes-blog-581.html
Read full article from 2001 -- Shortest Prefixes