poj 2001

http://poj.org/problem?id=2001
大意: 求一字符串的最短前缀
解题思路：trie树的简单应用。。直接模版即可
 1 #include <iostream>
 2 #include<cstring>
 3 using namespace std;
 4 struct node{
 5     int cnt;
 6     struct node *next[26];
 7     node(){//结构体中可以带函数，进行初始化
 8         cnt =0;
 9         memset(next,0,sizeof(next));
10     }
11 };
12 char str[1003][30];
13 node *root = NULL;//初始化，，根节点不用。。
14 
15 void maketrie(char *s){
16     node *p = root;
17     node *temp = NULL;
18     for(int i=0;i<strlen(s);i++){
19         if(p->next[s[i]-'a']==NULL){//查看节点中是否有此节点。。没有的话加上，有的话。。cnt++;
20             temp = new node;
21             p->next[s[i]-'a']=temp;
22         }
23         p = p->next[s[i]-'a'];
24         p->cnt++;
25     }
26 }
27 
28 void search(char *s){//输出。。如果其cnt==1 证明他是该字符串的最短前缀，没有于别的字符串公用该节点。
29     node *p =root;
30     for(int i=0;i<strlen(s);i++){
31         p = p->next[s[i]-'a'];
32         cout<<s[i];
33         if(p->cnt==1)
34             break;
35     }
36 }
37 
38 int main()
39 {
40     int num = 0;
41     root = new node;
42     while(cin>>str[num]){
43         maketrie(str[num]);
44         num++;
45     }
46 
47     for(int i=0;i<num;i++){
48         cout<<str[i]<<" ";
49         search(str[i]);
50         cout<<endl;
51     }
52     return 0;
53 }