首页 > 其他分享 >tire字典树

tire字典树

时间:2022-08-21 14:46:07浏览次数:86  
标签:cnt tire int ++ 单词 trie 字典

维护一个字符串集合,支持两种操作:

  1. I x 向集合中插入一个字符串 x
  1. Q x 询问一个字符串在集合中出现了多少次。

共有 N

个操作,输入的字符串总长度不超过 105

,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N

,表示操作数。

接下来 N

行,每行包含一个操作指令,指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x

在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗104

 

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; // trie要事先确定好可能出现的单词总长度
int trie[N][26], idx, cnt[N]; // trie存树,idx记录当前树延伸到的位置,cnt记录答案
void tire_insert(char c[]) // 向树中插入单词
{
    int p = 0;// 记录当前位于树的哪里
    for(int i = 0; c[i]; i ++ )
    {
        int t = c[i] - 'a';// 将字母转化成数字
        if(!trie[p][t]) trie[p][t] = ++ idx;// 由于0代表根或者不存在,故新节点从1开始
        p = trie[p][t];// 继续记录
    }
    cnt[p] ++ ;
}

int trie_query(char c[])// 查找单词格式
{
    int p = 0;
    for(int i = 0; c[i]; i ++ )
    {
        int t = c[i] - 'a';
        if(!trie[p][t]) return 0;// 与插入不同,当单词中间断开时,证明这个单词不存在
        p = trie[p][t];
    }
    return cnt[p];// 返回单词个数
}
int main()
{
    int t;
    char s[3], sx[N];
    scanf("%d", &t);
    while(t -- )
    {
        scanf("%s%s", s, sx);
        if(s[0] == 'I') tire_insert(sx);
        else printf("%d\n", trie_query(sx));
    }


    return 0;
}

 

标签:cnt,tire,int,++,单词,trie,字典
From: https://www.cnblogs.com/leyuo/p/16609976.html

相关文章

  • 字典排序
    importoperatordefdeal_dict_sort():x=[{'name':'Homer','age':39},{'name':'Bart','age':10}]lx=sorted(x,key=operator.itemgetter('age'),......
  • tire树,字符串统计
    Trie,又称字典树、单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串)。特点:利用字符串的公共前缀来减少查询......
  • 字典(dict)
    4.7字典(dict)字典是Python中一种非常重要的数据类型。字典和之前的列表、元组不同,里面的元素使用键-值对进行存储。通常字典中元素的键由字符串或数字等可哈希数据类型......
  • python 中 判断列表、元组、字符串、字典、集合为空的方法
     001、>>>test1=[]>>>test1[]>>>ifnottest1:##判断列表为空...print("noelement")...noelement 002、>>>test......
  • python数据类型---字典dict
    python数据类型---字典dict1.基本认识字典是Python里一种常用的数据类型,键值对,keyvalue对,它用于存放具有映射关系的数据。字典中的数据是无顺序的。。。。。。d={key......
  • 深入理解Redis 数据结构—字典
    字典,又称为符号表、关联数组或映射,是一种用于保存键值对的抽象数据结构。在字典中,一个键可以和一个值进行关联,这些关联的键和值称为键值对。键值对中键是唯一的,我们可以......
  • 字典序第k小数字
        https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solution/pythonjavajavascriptgo-di-gui-by-himymbe-5mq5/ funcfindKthNumber......
  • python 中输出字典中的键、值最小、最大的项
     001、输出最小、最大的键或者值>>>dict1={"c":800,"d":600,"a":900,"b":700}>>>dict1{'c':800,'d':600,'a':900,'b':700}>>>min(dict1)......
  • 列表元组字典字符串
    目录列表(List)有序元组(Tuple)有序字典(dictionary)无序字符串(String)很乱,等整理好了加进来列表(List)有序是其他语言的数组,但python支持存储不同类型数据,但通常只存......
  • Python 字典排序
    字典是“键-值对”的无序可变序列在实际运用中,对字典进行排序是一个比较常见的操作,主要用到了python内置函数sorted(),该函数可以对所有可迭代的对象进行排序操作。语法(pyth......