前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >trie树(字典树)-HDU1251

trie树(字典树)-HDU1251

作者头像
ACM算法日常
发布2018-08-07 19:41:03
1.1K0
发布2018-08-07 19:41:03
举报
文章被收录于专栏:ACM算法日常

trie树的实现比较简单。它使在字符串集合中查找某个字符串的操作的复杂度降到最大只需O(n),其中n为字符串的长度。trie是典型的将时间置换为空间的算法,好在ACM中一般对空间的要求很宽松。trie的原理是利用字符串集合中字符串的公共前缀来降低时间开销以达到提高效率的目的。 它具有以下性质:

  • 根结点不包含任何字符信息;
  • 如果字符的种数为n,则每个结点的出度为n(这样必然会导致浪费很多空间,这也是trie的缺点,还没有想到好点的办法避免);
  • 查找,插入复杂度为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,险过。

代码示例

map版本的实现

代码语言:javascript
复制
#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版本的。

代码语言:javascript
复制
#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';
        #如果该字符存在,串数量加1
        if(location->next[branch]) location->next[branch]->count++;
        #如果不存在,建新结点
        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;
}

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-01-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 代码示例
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档