专栏首页个人学习总结做题总结——单词查找树

做题总结——单词查找树

做题总结——单词查找树

题目

题意分析:

这道题目就是一道Trie树相关操作的题目(这道题目只涉及了插入操作),求最少的结点数目就相当于输出向Trie树中插入的最后一个结点的序号(注意开始就有根结点)

做题思路:

按照Trie树的模板来做即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5+5;
char s[100];
ll sum=1;  
int trie[maxn][70];      //这里是int类型,不是char类型,同时十足要开的大一些
void insert()           
{
    int len=strlen(s);
    int root=0,i;
    for(i=0;i<len;i++)
    {
        int u=s[i]-'A';
        if(!trie[root][u])
        {
            trie[root][u]=++sum;
        }
        root=trie[root][u];
    }
}
int main()
{
    //while(gets(s))
    while(~scanf("%s",s))
    {
        insert();
    }
    cout<<sum<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串查找----三向单词查找树

    SuperHeroes
  • 字符串查找----R向单词查找树

    SuperHeroes
  • 用 JavaScript 实现单词查找树

    对于搜索字符串的需求,在最坏的情况下,二叉搜索树的时间复杂度可能为 O(n),“n” 是二叉树中存储的字符串的总数量。所以为了在最佳时间内搜索字符串,需要一种性...

    疯狂的技术宅
  • hbase源码系列(五)Trie单词查找树

      在上一章中提到了编码压缩,讲了一个简单的DataBlockEncoding.PREFIX算法,它用的是前序编码压缩的算法,它搜索到时候,是全扫描的方式搜索的...

    岑玉海
  • 1729 单词查找树 2000年NOI全国竞赛

    1729 单词查找树 2000年NOI全国竞赛 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 D...

    attack
  • 算法(五)字典树算法快速查找单词前缀

    字典树,又称单词查找树,是一个典型的一对多的字符串匹配算法。“一”指的是一个模式串,“多”指的是多个模板串。字典树经常被用来统计、排序和保存大量的字符串。它利用...

    一只羊
  • 字典树概念与题型解析

    这次讲一个不经常被人提起的数据结构 - 字典树,虽说知名度不高,但是这个数据结构可以解决其他数据结构所不能解决,或者是比较难解决的问题,而且性能方面,相对于其他...

    五分钟学算法
  • 字典树概念与题型解析

    这次讲一个不经常被人提起的数据结构 - 字典树,虽说知名度不高,但是这个数据结构可以解决其他数据结构所不能解决,或者是比较难解决的问题,而且性能方面,相对于其他...

    暮雨
  • 字典树概念与题型解析

    这次讲一个不经常被人提起的数据结构 - 字典树,虽说知名度不高,但是这个数据结构可以解决其他数据结构所不能解决,或者是比较难解决的问题,而且性能方面,相对于其他...

    用户1564362
  • 经典算法题-矩阵中查找单词路径数

    cwl_java
  • 内存吞金兽(Elasticsearch)的那些事儿 -- 数据结构及巧妙算法

    ES 本质上是一个支持全文搜索的分布式内存数据库,特别适合用于构建搜索系统。ES 之所以能有非常好的全文搜索性能,最重要的原因就是采用了倒排索引。倒排索引是一种...

    房上的猫
  • 用 Python 分析《红楼梦》(1)

    專 欄 ❈楼宇,Python中文社区专栏作者。一位正在海外苦苦求学的本科生。初中时自学编程,后来又在几位良师的帮助下走上了计算机科学的道路。曾经的 OIer,...

    Python中文社区
  • 互信息和信息熵

    网址:https://blog.csdn.net/am290333566/article/details/81187124

    DC童生
  • 巧用 Trie 树实现搜索引擎关键词提示功能

    我们几乎每天都在用搜索引擎搜索信息,相信大家肯定有注意过这样一个细节:当输入某个字符的时候,搜索引框底下会出现多个推荐词,如下,输入「python」后,底下会出...

    kunge
  • 霍夫曼压缩算法

    felix
  • 前端学数据结构与算法(八): 单词前缀匹配神器-Trie树的实现及其应用

    继二叉树、堆之后,接下来介绍另外一种树型的数据结构-Trie树,也可以叫它前缀树、字典树。例如我们再搜索引擎里输入几个关键字之后,后续的内容会自动续上。此时我们...

    飞跃疯人院
  • 数据结构 | 30行代码,手把手带你实现Trie树

    今天是算法和数据结构专题的第28篇文章,我们一起来聊聊一个经典的字符串处理数据结构——Trie。

    TechFlow-承志
  • 怎么设计高效的敏感词过滤系统(一)

    IM项目需要对上边传输的消息进行必要的过滤。如果总是对着某人输入f**k就显得不太文明了。

    普通程序员
  • 新一代搜索引擎项目 ZeroSearch 设计探索

    ? 本文作者:kaelhua,腾讯 WXG 后台开发工程师 背景 写这篇文章很大的原因在于不论是内网还是外网,分享内存检索引擎设计的资料都非常稀少,且存量的资...

    腾讯技术工程官方号

扫码关注云+社区

领取腾讯云代金券