Shortest Prefixes （最短前缀且不重复）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <string>
 4 #include <iostream>
 5 #include <stdlib.h>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 const int MAX_NODE = 300001;
10 const int CHARSET = 26;
11 
12 int trie[MAX_NODE][CHARSET]={0};
13 //int color[MAX_NODE]={0};
14 int vis[MAX_NODE]={0};
15 int k = 1;
16 char s[MAX_NODE][1000];
17 
18 void insert(char w[])
19 {
20     int len = strlen(w);
21     int p = 0;  // 根结点
22     for (int i=0;i<len;i++)
23     {
24         int c = w[i] - ‘a‘;
25         if (!trie[p][c])
26         {
27             trie[p][c] = k;
28             k++;
29         }
30         p = trie[p][c];
31         vis[p]++;
32     }
33     //color[p] = 1;
34 }
35 
36 
37 void search(char s[])
38 {
39     int len = strlen(s);
40     int p = 0;
41     for (int i=0;i<len;i++)
42     {
43         if (vis[p] == 1)
44             break;
45         int c = s[i]-‘a‘;
46         printf("%c",s[i]);
47         p = trie[p][c];
48 
49     }
50 }
51 
52 
53 int main()
54 {
55 #ifndef ONLINE_JUDGE
56     freopen("../in.txt", "r", stdin);
57 #endif
58     int t = 0;
59     while (scanf("%s",s[t])!=EOF)
60     {
61         insert(s[t]);
62        // cout << s[t] << endl;
63         t++;
64     }
65     //cout << t << endl;
66     for (int i=0;i<t;i++)
67     {
68         printf("%s ",s[i]);
69         search(s[i]);
70         printf("\n");
71     }
72     return 0;
73 }