精华内容
下载资源
问答
  • Trie树 应用于统计和排序

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   

     1. 什么是trie树

      1.Trie树 (特例结构树)  

          Trie树,又称单词查找树、字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
         Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
         Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

    2.  三个基本特性:  

    1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。  
    2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。 
    3)每个节点的所有子节点包含的字符都不相同。

    3 .例子

           和二叉查找树不同,在trie树中,每个结点上并非存储一个元素。
           trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。
           在trie树上进行检索类似于查阅英语词典。
          一棵m度的trie树或者为空,或者由m棵m度的trie树构成。

         例如,电子英文词典,为了方便用户快速检索英语单词,可以建立一棵trie树。例如词典由下面的单词成:a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba


               再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:

            

            可以看出:

    • 每条边对应一个字母。
    • 每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。
    • 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

    查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。

     2. trie树的实现

    1.插入过程

    对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入trie树。

    2. 查找过程

    其方法为:

    (1) 从根结点开始一次搜索;

    (2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;

    (3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
    (4) 迭代过程……
    (5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。其他操作类似处理.

           即从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。如下图中:trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。  

          


    代码:
    // stdafx.h : include file for standard system include files,// or project specific include files that are used frequently, but// are changed infrequently//#pragma once#include <stdio.h>  #include "stdlib.h"#include <iostream>#include <string.h>using namespace std;//宏定义    #define TRUE   1    #define FALSE   0   #define NULL 0#define OK    1    #define ERROR   0  #define INFEASIBLE -1    #define OVERFLOW -2  const int num_chars = 26;class Trie {public:    Trie();    Trie(Trie& tr);    virtual ~Trie();    int trie_search(const char* word, char* entry ) const;    int insert(const char* word, const char* entry);    int remove(const char* word, char* entry);protected:     struct Trie_node{           char* data; //若不为空,表示从root到此结点构成一个单词            Trie_node* branch[num_chars]; //分支            Trie_node(); //构造函数      };          Trie_node* root; //根结点(指针) };

    // Test.cpp : Defines the entry point for the console application.  //  #include "stdafx.h" Trie::Trie_node::Trie_node() { data = NULL;     for (int i=0; i<num_chars; ++i)   branch[i] = NULL;}Trie::Trie():root(NULL) {}Trie::~Trie(){}int Trie::trie_search(const char* word, char* entry ) const {   int position = 0//层数  char char_code;     Trie_node *location = root;  //从根结点开始  while( location!=NULL && *word!=0 ) {       if (*word >= 'A' && *word <= 'Z')    char_code = *word-'A';       else if (*word>='a' && *word<='z')    char_code = *word-'a';       else return 0;// 不合法的单词     //转入相应分支指针   location = location->branch[char_code];       position++;       word++;   }   //找到,获取数据,成功返回  if ( location != NULL && location->data != NULL ) {       strcpy(entry,location->data);       return 1;   }   else  return 0;// 不合法的单词}int Trie::insert(const char* word, const char* entry) {    int result = 1, position = 0;    if ( root == NULL ) root = new Trie_node;   //初始插入,根结点为空  char char_code;    Trie_node *location = root;   //从根结点开始  while( location!=NULL && *word!=0 ) {         if (*word>='A' && *word<='Z') char_code = *word-'A';         else if (*word>='a' && *word<='z') char_code = *word-'a';         else return 0;// 不合法的单词      //不存在此分支   if( location->branch[char_code] == NULL )               location->branch[char_code] = new Trie_node;    //创建空分支     //转入分支   location = location->branch[char_code];         position++;word++;   }    if (location->data != NULL) result = 0;//欲插入的单词已经存在     else {    //插入数据       location->data = new char[strlen(entry)+1];     //分配内存      strcpy(location->data, entry);    //给data赋值表明单词存在  }    return result; }int main(){    Trie t;    char entry[100];    t.insert("a", "DET");         t.insert("abacus","NOUN");    t.insert("abalone","NOUN");    t.insert("abandon","VERB");    t.insert("abandoned","ADJ");   t.insert("abashed","ADJ");    t.insert("abate","VERB");     t.insert("this", "PRON");    if (t.trie_search("this", entry))        cout<<"'this' was found. pos: "<<entry<<endl;    if (t.trie_search("abate", entry))        cout<<"'abate' is found. pos: "<<entry<<endl;    if (t.trie_search("baby", entry))        cout<<"'baby' is found. pos: "<<entry<<endl;    else        cout<<"'baby' does not exist at all!"<<endl;}


    3. 查找分析

           在trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。
           如果要查找的关键字可以分解成字符序列且不是很长,利用trie树查找速度优于二叉查找树。如:
           若关键字长度最大是5,则利用trie树,利用5次比较可以从26^5=11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行次比较。

    3. trie树的应用:

    1. 字符串检索,词频统计,搜索引擎的热门查询

            事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

            举例:

           1)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

           2)给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。

           3)给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

           4)1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串

           5)寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。

    2. 字符串最长公共前缀

           Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。举例:

          1) 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少.  解决方案:

            首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线  (Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。

           而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

            1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;

            2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;


    3.  排序

           Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。

            举例: 给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

    4 作为其他数据结构和算法的辅助结构

           如后缀树,AC自动机等。




               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • PHP-Trie树应用

    2019-05-19 11:04:16
    一、Trie树简介 什么是Trie树Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本...

     

    一、Trie树简介

    什么是Trie树?  

    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。   Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    Trie树基本性质:  

    1、根节点不包含字符,除根节点外每一个节点都只包含一个字符。   2、从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。   3、每个节点的所有子节点包含的字符都不相同。

    二、Trie树操作

    插入操作示例:

    class TTrie
    {
        private $dict = [[]]; //字典
        private $input = 0; //字符串当前偏移
        private $backtracking = 0; //字符串回溯位置
        private $buffer = [];
    
        public function __construct($words)
        {
            $this->insert($words);
        }
    
        /**
         * 插入单词
         * Function insert
         * @Author sakmon
         * @CreateTime 2019/4/25 15:42
         * @param $word
         */
        public function insert($word)
        {
            if (is_array($word)) {
                foreach ($word as $v) {
                    $this->insert($v);
                }
                return;
            }
            $p = count($this->dict);
            $cur = 0; //当前节点号
            foreach (str_split($word) as $c) {
                if (isset($this->dict[$cur][$c])) { //已存在就下移 , 相同前缀单词同一个节点
                    $cur = $this->dict[$cur][$c];
                    continue;
                }
                $this->dict[$p] = []; //创建新节点
                $this->dict[$cur][$c] = $p; //在父节点记录子节点号
                $cur = $p; //把当前节点设为新插入的
                $p++;
            }
            $this->dict[$cur]['isWord'] = true; //一个词结束,标记叶子节点
        }
    }
    

    字典树生成示例:

    $trie = new TTrie();
    $words = [‘abd’, ‘abc’, ‘bd’, ‘dd’, ‘dda’]; 
    foreach ($words as $word) {
        $trie->insert($word);
    }
    

    单词查找示例:

        /**
         * 单词查找
         * Function find
         * @Author sakmon
         * @CreateTime 2019/4/25 17:24
         * @param $word
         * @return bool
         */
        public function find($word)
        {
            $len = strlen($word);
            $p = 0;
            for ($i = 0; $i < $len; $i++) {
                $c = $word{$i};
                if (!isset($this->dict[$p][$c])) { //节点不存在
                    return false;
                }
                $p = $this->dict[$p][$c]; //子节点
            }
            if (!isset($this->dict[$p]['isWord'])) {  //判断是否为单词,避免相同前缀
                return false;
            }
            return true;
        }

    删除单词:

        /**
         * Function remove
         * @Author sakmon
         * @CreateTime 2019/4/26 11:54
         * @param $word
         */
        public function remove($word)
        {
            if (!$this->find($word)) { //先判断单词是否存在
                return false;
            }
            $len = strlen($word);
            $p = 0;
            $del = []; //需删除的相关联键
            for ($i = 0; $i < $len; $i++) {
                $c = $word{$i};
                $cur = $this->dict[$p][$c]; //子节点
                if (count($this->dict[$cur]) == 1) {
                    $del[] = [$p, $c];
                } else {
                    $del = [];
                }
                $p = $cur; //子节点
            }
            foreach ($del as $key => $val) {
                unset($this->dict[$val[0]][$val[1]]);
            }
            if (count($this->dict[$p]) == 1) { //判断叶子是否只有一个元素,即isWord
                unset($this->dict[$p]);
            } else {
                unset($this->dict[$p]['isWord']);
            }
            return true;
        }

    三、Trie树应用

    /**
         * Function match
         * @Author sakmon
         * @CreateTime 2019/4/25 18:03
         * @param $s
         * @return array
         */
        public function match($s)
        {
            $cur = 0; //当前节点,初始为根节点
            $i =& $this->input; //字符串当前偏移
            $p =& $this->backtracking; //字符串回溯位置
            $len = strlen($s);
            $dl = 0;
            while ($i < $len) {
                $c = $s{$i};
                if (isset($this->dict[$cur][$c])) { //如果存在
                    $cur = $this->dict[$cur][$c]; //转到对应的位置
                    if (isset($this->dict[$cur]['isWord'])) { //是叶子节点,单词匹配!
                        $dl = $i - $p + 1; //最长匹配单词长度
                    }
                    if (isset($this->dict[$cur][$s[$i + 1]])) {//检查下一个字符是否也能匹配,长度优先
                        $i++;
                        continue;
                    }
                    if ($dl > 0) { //匹配单词成功
                        $this->buffer[] = substr($s, $p, $dl); //取出匹配位置和匹配的词
                        $i = $p + $dl - 1;
                        $p = $i + 1;
                        $dl = 0;
                    } else {
                        $p = $i + 1; //设置下一个回溯位置
                    }
                    $cur = 0; //重置当前节点为根节点
                } else { //不匹配
                    $cur = 0; //重置当前节点为根节点
                    $i = $p; //把当前偏移设为回溯位置
                    $p = $i + 1; //设置下一个回溯位置
                }
                $i++; //下一个字符
            }
            return $this->buffer;
        }

    字符串检索示例 :

    include_once('keywords.php');
    $words = array_column($keywords , 'word');
    $trie = new TTrie($words);
    //$matches = $trie->match('近年来,厦门聚焦发展电子信息、装备制造等五大产业集群,重点打造平板显示、半导体和华秋集成电路等12条千亿产业链,日前厦门发改委发布其招商地图及投资机会清单,对华强半导体与集成电路领域作出招商引资规划。');
    $matches = $trie->match('
    5G究竟会给全球带来怎样的影响力?为何号称全球第一的美国屡屡对一中国企业处处压制,而不惜采用各种手段抹黑且极力阻止其开拓市场。这些行为对华为后面有何影响,勇敢的华为会否赢得5G跑道的比赛?
    重大事件回顾
     
    去年12月,加拿大当局逮捕了华为首席财务官孟晚舟,以便向美国政府提出引渡请求。美国政府声称该公司通过隐瞒伊朗支付违反对该国的制裁来欺骗几家银行。
     
    今年1月,司法部宣布对该公司的两个部门提出一系列指控,包括窃取T-Mobile USA的商业机密。同时,美国特朗普政府通过2019年的国防授权法禁止华为和中兴参与美国政府的大部分项目合作。
     
    5月2日~3日,以美国特朗普政府为首,加拿大、澳大利亚、以色列、部分欧盟成员国(德国、法国、英国等)以及日本和韩国等30个国家在布拉格举行5G网络安全协议,并发布名为“布拉格提议”的声明。其中意味不言而喻,剑指中国华为。
     
    5月15日,美国特朗普签署行政命令。其内容用意一句话来概括就是将华为列入黑名单,禁止其电信设备进入美国市场。该文件发布后,又将华为旗下70个子公司列入美国贸易黑名单。
     
    华为为何受“照顾”
     
    5g技术的重要性不言而喻,它将为我们社会带来全新的繁荣。它将促发各行各业许多新的东西,如远程医疗、自动驾驶、智慧城市、智慧工业等,以及赋予我们身边很多最基础的设施,如配电。这将使得它会成为我们生活中非常重要的一个部分。
     
    然而,5G技术的竞争已经在进行中,而华为公司已经处于全球领先的地位。这一点或许是美国害怕和担心的。害怕的是一旦使用外国网络设备导致未来一些不可控因素的发生;担心的是5G领域已经落后于中国,美国全球5G影响力地位下降。
     
    而这些所谓的“害怕”,华为已经多次强调并解释。过去三十年,华为一直保持良好的网络安全记录。去年年底华为追加投入20亿美元的初始专项预算升级网络系统软件。
     
    但挥不去地总不是这些阴影,而是背后的“阴谋”。最近,美国官员一直以“网络安全”为由,禁止华为与美国政府签订合同,并敦促美国盟友也效仿。但是至今为止除了澳大利亚和日本以外,他们遭到了许多海外盟友的怀疑。
     
    正如今天许多媒体报道的那样,美国特朗普政府15日再次挥舞权利的大棒意图遏制华为。不管是去年12月的孟晚舟被羁押事件,还是周三特朗普签署的行政命令,其意图已相当明显。
     
    外界认为,不管是华为、爱立信,诺基亚和三星......,无论美国选择谁?都不该将政治权利导入商业竞争。
     
    对华为影响如何?
     
    然而,更大的担忧可能是美国将华为列入美国商务部工业和安全局(BIS)所谓的实体名单。这意味着美国公司需要获得相关许可才能向华为出售或转让技术。而华为依赖英特尔和高通等美国公司的部分组件来生产智能手机和笔记本电脑。
     
    此外,华为的消费者业务现在是收入最大的部门,占其总营收48.4%,被视为该公司的主要成长动能。对消费者群体的任何干扰都可能影响其整体业务。
     
    但在过去几年中,华为一直在为其智能手机设计自己的芯片,以减少对其他公司的依赖。它有一系列称为Kirin的处理器和Balong 5000的调制解调器,搭载这些产品的设备将被允许连接到5G网络。
     
    据IDC数据显示,在2018年,73%的华为智能手机包含了该公司自己的芯片。另外10%来自台湾的联发科技公司。剩下的17%来自高通公司,但这些主要是针对低端200美元以下的手机。
     
    据笔者观察,如果美国特朗普政府铁心不与华为合作5G,在失去美国5G市场的同时,如果BIS有选择性的限制华为与美国企业合作,对华为ICT基础设施和部分智能终端设备的部件供货将会产生一定影响。
     
    尽管如此,我们也有必要强调,美国只是世界的一部分。华为5G不会因为西方变黑,而东方不闪耀。
    ');
    print_r($matches);
    exit;

     

    展开全文
  • AVL树,红黑树,B树,B+树,Trie树应用场景简介 AVL树:平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1)...
    AVL树,红黑树,B树,B+树,Trie树应用场景简介

            AVL树:平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1),只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL适合用于插入删除次数比较少,但查找多的情况。

    应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL


            红黑树:平衡二叉树,通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,确保没有一条路径会比其他路径长2倍,因而是近似平衡的。所以相对于严格要求平衡的AVL树来说,它的旋转保持平衡次数较少。用于搜索时,插入删除次数多的情况下我们就用红黑树来取代AVL

    红黑树应用比较广泛:

    ·        广泛用在C++STL中。mapset都是用红黑树实现的。

    ·        著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

    ·        epoll在内核中的实现,用红黑树管理事件块

    ·        nginx中,用红黑树管理timer

    ·        JavaTreeMap实现


            B树,B+树:它们特点是一样的,是多路查找树,一般用于数据库中做索引,因为它们分支多层数少,因为磁盘IO是非常耗时的,而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。
    B+树是
    B树的变种树,有n棵子树的节点中含有n个关键字,每个关键字不保存数据,只用来索引,数据都保存在叶子节点。是为文件系统而生的。

            B+树相对B树磁盘读写代价更低:因为B+树非叶子结点只存储键值,单个节点占空间小,索引块能够存储更多的节点,从磁盘读索引时所需的索引块更少,所以索引查找时I/O次数较B-Tree索引少,效率更高。而且B+Tree在叶子节点存放的记录以链表的形式链接,范围查找或遍历效率更高Mysql InnoDB用的就是B+Tree索引。


    Trie树:

            又名单词查找树,一种树形结构,常用来操作字符串。它是不同字符串的相同前缀只保存一份
    相对直接保存字符串肯定是节省空间的,但是它保存大量字符串时会很耗费内存(是内存)。
    类似的有:前缀树(prefix tree),后缀树(suffix tree)radix tree(patricia tree, compactprefix tree)crit-bit tree(解决耗费内存问题),以及前面说的double array trie
    前缀树:字符串快速检索,字符串排序,最长公共前缀,自动匹配前缀显示后缀。
    后缀树:查找字符串s1在s2中,字符串s1在s2中出现的次数,字符串s1,s2最长公共部分,最长回文串。

    trie 树的一个典型应用是前缀匹配,比如下面这个很常见的场景,在我们输入时,搜索引擎会给予提示。



    还有比如IP选路,也是前缀匹配,一定程度会用到trie。

    展开全文
  • HDU 1277 全文检索 (Trie树应用 好题)

    千次阅读 2015-02-23 23:32:08
    HDU 1277 全文检索 (trie树应用 好题)

    全文检索

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

    Total Submission(s): 1304    Accepted Submission(s): 416

    Problem Description
    我们大家经常用google检索信息,但是检索信息的程序是很困难编写的;现在请你编写一个简单的全文检索程序。
    问题的描述是这样的:给定一个信息流文件,信息完全有数字组成,数字个数不超过60000个,但也不少于60个;再给定一个关键字集合,其中关键字个数不超过10000个,每个关键字的信息数字不超过60个,但也不少于5个;两个不同的关键字的前4个数字是不相同的;由于流文件太长,已经把它分成多行;请你编写一个程序检索出有那些关键字在文件中出现过。
     

    Input
    第一行是两个整数M,N;M表示数字信息的行数,N表示关键字的个数;接着是M行信息数字,然后是一个空行;再接着是N行关键字;每个关键字的形式是:[Key No. 1] 84336606737854833158。
     

    Output
    输出只有一行,如果检索到有关键字出现,则依次输出,但不能重复,中间有空格,形式如:Found key: [Key No. 9] [Key No. 5];如果没找到,则输出形如:No key can be found !。
     

    Sample Input
    20 10 646371829920732613433350295911348731863560763634906583816269 637943246892596447991938395877747771811648872332524287543417 420073458038799863383943942530626367011418831418830378814827 679789991249141417051280978492595526784382732523080941390128 848936060512743730770176538411912533308591624872304820548423 057714962038959390276719431970894771269272915078424294911604 285668850536322870175463184619212279227080486085232196545993 274120348544992476883699966392847818898765000210113407285843 826588950728649155284642040381621412034311030525211673826615 398392584951483398200573382259746978916038978673319211750951 759887080899375947416778162964542298155439321112519055818097 642777682095251801728347934613082147096788006630252328830397 651057159088107635467760822355648170303701893489665828841446 069075452303785944262412169703756833446978261465128188378490 310770144518810438159567647733036073099159346768788307780542 503526691711872185060586699672220882332373316019934540754940 773329948050821544112511169610221737386427076709247489217919 035158663949436676762790541915664544880091332011868983231199 331629190771638894322709719381139120258155869538381417179544 000361739177065479939154438487026200359760114591903421347697 [Key No. 1] 934134543994403697353070375063 [Key No. 2] 261985859328131064098820791211 [Key No. 3] 306654944587896551585198958148 [Key No. 4] 338705582224622197932744664740 [Key No. 5] 619212279227080486085232196545 [Key No. 6] 333721611669515948347341113196 [Key No. 7] 558413268297940936497001402385 [Key No. 8] 212078302886403292548019629313 [Key No. 9] 877747771811648872332524287543 [Key No. 10] 488616113330539801137218227609
     

    Sample Output
    Found key: [Key No. 9] [Key No. 5]
     
    Author
    Cai Minglun
     
    Source
    杭电ACM集训队训练赛(VI)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1277

    题目分析:网上貌似都是ac自动机搞的,这里用trie树搞一下,跑了62ms,读入用getchar记录下换行次数,对key字符串建字典树,枚举流文件的后缀到字典树中查找,再用hash标记一下


    #include <cstdio>
    #include <cstring>
    char t[60005], tmp[10], key[65];
    bool hash[60005];
    
    struct node
    {
        node *next[10];
        int id;
        node()
        {
            memset(next, NULL, sizeof(next));
            id = -1;
        }
    };
    
    void Insert(node *p, char *s, int id)
    {
        for(int i = 0; s[i] != '\0'; i++)
        {
            int idx = s[i] - '0';
            if(p -> next[idx] == NULL)
                p -> next[idx] = new node();
            p = p -> next[idx];
        }
        p -> id = id;
    }
    
    void Search(node *p, char *s)
    {
        for(int i = 0; s[i] != '\0'; i++)
        {
            int idx = s[i] - '0';
            if(p -> id != -1 && !hash[p -> id])
            {
                printf(" [Key No. %d]", p -> id);
                hash[p -> id] = true;
            }
            if(p -> next[idx] == NULL)
                return;
            p = p -> next[idx];
        }
    }
    
    int main()
    {
        int n, m, cnt1 = 0, cnt2 = 0;
        scanf("%d %d", &m, &n); 
        getchar();
        while(cnt2 < m)
        {
            char ch = getchar();
            if(ch == '\n')
                cnt2++;
            else
                t[cnt1++] = ch;
        }
        t[cnt1] = '\0';
        node *root = new node();
        memset(hash, false, sizeof(hash));
        for(int i = 1; i <= n; i++)
        {
            //tmp读取"[Key","No.","1] "这些没用字符串
            scanf("%s%s%s%s", tmp, tmp, tmp, key);
            Insert(root, key, i);
        }
        printf("Found key:");
        for(int i = 0; t[i] != '\0'; i++)
            Search(root, t + i);
        printf("\n");
    }


    展开全文
  • POJ 2001 Shortest Prefixes (Trie树应用 好题)
  • 红黑树是近似的平衡二叉树AVL,损失了一定的平衡性,来降低维护平衡所需的代价。...Trie树又叫检索树、字典树,主要是对字符串内容建索引,对前缀查找速度要求很高的场景。耗内存,查找速度快,但插入、删...
  • Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大...
  • Trie树应用(字典树)

    2013-04-05 13:42:00
    某同学的同学摩根电面的一道题目: 有一个大的textfile,里面很多英文单词,查找重复出现的单词; 题目的简单:全部遍历太慢,考官说太慢...能,使用强大的Trie吧! 使用stl的map实现: #pragma warning(disabl...
  • HDU 1671——Trie树应用

    2015-12-28 16:40:04
    ... 题意:给定一些字符串,判断是否存在一些字符串是其他字符串的前缀。如:第一组数据 911 是最后一个 ...91125426 的前缀,故拨打时容易直接... //数据有多组,记得清空字典 } return 0; }
  • UVA 11732 Trie树应用

    2013-04-10 12:16:00
    Trie树上每往下走一层、就计算一次、、这样就不会重复计算 #include #include < string .h> #include #include #include #include #include #define sigma_size 26 using namespace std; ...
  • Trie树基本应用,先建树,而后对每个字符串查询,在查询过程中,取第一次碰到的尾缀单词数为1的结点之前的字符串作为前缀,如果查询完都没有,则取本身为前缀。 【代码】 #include #include #include typedef ...
  • Trie树 应用 Phone List

    2012-06-15 11:21:55
    字符串处理的算法有很多,Trie树和Trie图(也就是AC自动机)都是很高效的数据结构,后缀数组也 是,但是由于后缀数组较为复杂,实现起来也比较恼火。Trie树是一棵度 m ≥ 2 的树,它的每一层分支不是靠整个关键码的...
  • Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点. <br />其基本性质可以归纳为: 1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。  ...
  • 思路: Trie树应用,注意输入的如果不是有长度一样的,需要特殊处理一下, 我是先记录一下第一个点出现的个数,然后找孩子节点,找的过程中减去孩子节点的兄弟节点的个数, 就得出了答案。   #include #...
  • POJ3630: 给定 个长度不超过 的数字串,问其中是否存在两个数字串 ,使得 是 的前缀,多组数据. 输入格式 第一行一个整数 ,表示数据组数。 对于每组数据,第一行一个数 ,接下来 行输入 个数字串。...
  • Phone List Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 25280 Accepted: 7678 Description ...Given a list of phone numbers, determine if it is consis...
  • Trie树

    千次阅读 2018-04-07 17:54:57
    Trie树 标签(空格分隔): 数据结构 算法知识文档 Trie树 应用: trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。 给你一个字典...
  • Trie树应用

    2014-07-01 22:46:17
    Trie树是一种空间换时间的字典树,我自己一般叫它为26叉树,还有一种类似的树是 三叉树 ,可以用来做自动补全算法,这项算法可以用来做搜索引擎的自动搜索补全功能。 下面仅仅 以我自己对Trie树的理解来看看Trie...
  • Trie树及其应用

    千次阅读 2013-01-06 21:37:29
    Trie树 可参照百度百科: ...   二 Trie树的构造及应用 /* This is a free Program, You can modify or redistribute it under the terms of GNU *Description:Trie树及其应用 *Language: C++ *
  • Trie树详解及其应用

    2019-02-17 16:15:02
    Trie树详解及其应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,714
精华内容 685
关键字:

trie树应用