字典树(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，险过。

my code1:

 

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
    int i,j,k,len;
    string str;char temp[15],temp1[15];
    map <string,int> mymap;
    while(gets(temp))
    {
        if(temp[0]=='\n') break;
        len=strlen(temp);
        if(len==0) break;
        for(i=0;i<len;i++)//求出某个字符串的所有前缀,并用MAP存起来
        {
            for(j=0;j<=i;j++) temp1[j]=temp[j];temp1[j]='\0';
            str.assign(temp1);
            mymap[str]++;
        }
    }
    while(scanf("%s",&temp)!=EOF)
        cout<<mymap[temp]<<endl;//此时直接输出结果即可
    return 0;
}

用MAP的特点是代码短，思路简单，很容易实现，但耗时大。下面给出trie版本的。

my code2:

#include<iostream>
using namespace std;

const int kind=26;//字母种类

struct Treenode//树的结点结构
{
    int count;//这个附加变量在本题中记录遍历到该结点形成的字符串出现的次数，在不同题中可记录不同的内容。
    Treenode *next[kind];//指向儿子结点
    Treenode()//每个结点的初始化
    {
        count=1;
        for(int i=0;i<kind;i++)
            next[i]=NULL;
    }
};

void insert(Treenode *&root,char *word)//向以root为根结点的树中插入串word
{
    Treenode *location=root;
    int i=0,branch=0;
    
    if(location==NULL) {location=new Treenode();root=location;}

    while(word[i])
    {
        branch=word[i]-'a';
        if(location->next[branch]) location->next[branch]->count++;//如果该字符存在，串数量加1
        else location->next[branch]=new Treenode();//如果不存在，建新结点
        i++;
        location=location->next[branch];
    }
}

int search(Treenode *root,char *word)//查找，与插入类似
{
    Treenode *location=root;
    int i=0,branch=0,ans;

    if(location==NULL) return 0;

    while(word[i])
    {
        branch=word[i]-'a';
        if(!location->next[branch]) return 0;
        i++;
        location=location->next[branch];
        ans=location->count;
    }
    return ans;
}
int main()
{
    char word[10];
    char ask[10];
    Treenode *root=NULL;
    while(gets(word))
    {
        if(word[0]=='\0') break;
        insert(root,word);
    }
    while(gets(ask))
        cout<<search(root,ask)<<endl;
    return 0;
}

上述代码中插入和查找可当模板来用了。。。