字典樹(trie tree)

     今天AC了兩題trie tree的題目,感覺trie的性質真的是相當的好，而且實現比較簡單。它使在字符串集合中查找某個字符串的操作的復雜度降到最大只需O(n),其中n為字符串的長度。trie是典型的將時間置換為空間的算法，好在ACM中一般對空間的要求很寬松。

     trie的原理是利用字符串集合中字符串的公共前綴來降低時間開銷以達到提高效率的目的。

它具有以下性質:1,根結點不包含任何字符信息;2,如果字符的種數為n,則每個結點的出度為n(這樣必然會導致浪費很多空間,這也是trie的缺點,我還沒有想到好點的辦法避免);3,查找，插入復雜度為O(n),n為字符串長度。

    舉一個例子,給50000個由小寫字母構成的長度不超過10的單詞,然后問某個公共前綴是否出現過。如果我們直接從字符串集中從頭往后搜，看給定的字符串是否為字符串集中某個字符串的前綴，那樣復雜度為O(50000^2)，這樣顯然會TLE。又或是我們對于字符串集中的每個字符串，我們用MAP存下它所有的前綴。然后詢問時可以直接給出結果。這樣復雜度為O(50000*len),最壞情況下len為字符串最長字符串的長度。而且這沒有算建立MAP存儲的時間，也沒有算用MAP查詢的時間，實際效率會更低。但如果我們用trie的話，當查詢如字符串abcd是否為某字符串的前綴時，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。實際查詢復雜度只有O(len)，建立trie的復雜度為O(50000).這是完全可以接受的。

    如給定字符串集合abcd,abd,cdd,efg,hij,hi六個字符串建立的trie tree如下圖所示:

  

    查找一個字符串時，我們只需從根結點按字符串中字符出現順序依次往下走。如果到最后字符串結束時，對應的結點標記為紅色，則該字符串存在;否則不存在。

    插入時也只需從根結點往下遍歷，碰到已存在的字符結點就往下遍歷，否則，建立新結點;最后標記最后一個字符的結點為紅色即可。

    同時我們看到,如果字符的種類為n，則需要結點的個數為n級數。(誰有好辦法降低空間開銷,請告訴我)

 

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

題目:http://acm.hdu.edu.cn/showproblem.php?pid=1251

題目和我上面舉的例子差不多，是說給定一個字符串集合，然后每次詢問時給出一個字符串，問以該字符串為前綴的字符串在集合中有多少個。先給個用MAP版本的，限時2000MS的題目，用MAP，1750MS，險過。

 我的代碼：

 1#include<iostream>
 2using namespace  std;
 3const int kind=26;
 4struct trienode{
 5    public:
 6    trienode *next[kind];    
 7    int branch;
 8    trienode()
 9    {
10     branch=0;
11     for(int i=0;i<kind;i++)
12     next[i]=NULL;    
13    }
14};
15class trie{
16
17    trienode *root;
18    public:
19    trie(){root=NULL;}
20    void insert(char s[])
21    {
22        trienode *location=root;
23        if(location==NULL)
24        location=root=new trienode();
25        int i=0,k;
26        while(s[i])
27        {
28            k=s[i]-'a';
29            if(location->next[k])
30                location->next[k]->branch++;
31            else
32            {
33                location->next[k]=new trienode();
34                location->next[k]->branch++;    
35            }
36            i++;
37            location=location->next[k];    
38        }
39    }
40    int search(char s[]){
41        trienode *location=root;
42        if(!location) return 0;
43        int k,i=0,ans;
44        while(s[i])
45        {
46            k=s[i]-'a';
47            if(!location->next[k])    
48             return 0;
49            ans=location->next[k]->branch;
50            location=location->next[k];
51            i++;
52        }    
53        return ans;
54    }    
55    
56};
57int main()
58{
59    char a[100];
60    int i;
61    trie mytrie;
62    while(gets(a))
63    {
64        if(a[0]=='\0')
65        break;
66        mytrie.insert(a);    
67    }
68    while(gets(a)!=NULL)
69    {
70        //if(a=="end")
71        
72        printf("%d\n",mytrie.search(a));    
73    }
74    return 0;
75}
76