Trie

Trie樹，字典樹，可以用於串的快速檢索，串的排序和求最長公共前綴，他的結構大概是這樣的：

e.g.對於數字的字符串來說，Trie的結構體會包含一個next數組，存放1－10，就是數組大小為10，每個節點都指向一個這樣的數組；

0　0　0　0　0　0　0　0　0　0

然後，假如讀入的字符串第一位是9，那麼根的next數組的第九位就置為1，變成：

0　0　0　0　0　0　0　0　1　0

那麼第九位又接著對應這個位置上的next數組，假如下以為讀入1，那麼變成：

0　0　0　0　0　0　0　0　1　0

　　　　　　　1　0　0　0　0　0　0　0　0　0

所以字典樹的儲存形式就是這樣的一個樹形結構，而Trie結構體還可以再加上一個標誌位flag表示一個字符串結束，這樣就可以用於判斷前綴了...

需要其他功能的話可以再在結構體裡面加，比如加個count計數之類的，如果有需要的話...

下面這題就是判斷每個電話號碼是否是別的電話號碼的前綴，只要找到一個就行...

如果短的找長的，可以通過找到尾之後，掃一邊next數組，如果不是空的，就代表後面還有，就是前綴了；

如果長的找到短的，就會讀到flag=1的標誌位，也是前綴了：

poj 3630.Phone List

 1 // poj 3630.Phone List
 2 // 字典樹(trie樹) 找是否有電話號碼是別的電話號碼的前綴 
 3 // 
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <cstring>
 7 
 8 #define MAXN 11        //1-10
 9 
10 using namespace std;
11 
12 struct Trie {
13     Trie *next[MAXN];    //1-10
14     int flag;
15 };
16 
17 Trie node[1000001];        //靜態 
18 char s[11];
19 
20 int createTrie(char *s, Trie* &root, int &count)
21 {
22     int len = strlen(s);
23     Trie *p = root;
24     for(int i=0; i<len; i++)
25     {
26         int id = s[i] - '0';        
27         if(p->next[id] == NULL)
28         {
29             node[count].flag = 0;
30             for(int j=0; j<MAXN; j++)
31                 node[count].next[j] = NULL;
32             p->next[id] = &node[count++];
33         }
34         p = p->next[id];
35         if(p->flag == 1)    //e.g.9112找到前缀911 
36             return 0; 
37     }
38     for(int i=0; i<MAXN; i++)
39     {
40         if(p->next[i] != NULL)    //e.g.911前缀找到9112 
41             return 0;
42     }               
43     p->flag = 1;
44     return 1;
45 }
46 
47 int main()
48 {
49     int t, n;
50     scanf("%d", &t);
51     while(t--)
52     {
53         Trie *root = new Trie; //注意对root的初始化 
54         root->flag = 0;
55         for(int i=0; i<MAXN; i++)
56             root->next[i] = NULL;
57         int flag=0;
58         int count=0;
59         scanf("%d", &n);
60         for(int i=0; i<n; i++)
61         {
62             scanf("%s", &s);
63             if(!createTrie(s, root, count))
64             {
65                 flag = 1;
66                 //break;      
67             }                               
68         }
69         if(flag)
70             printf("NO
");
71         else
72             printf("YES
");
73     }
74     return 0;
75 }