首页 > 其他分享 >【Tire树】高效统计字符串

【Tire树】高效统计字符串

时间:2023-02-25 17:34:19浏览次数:33  
标签:高效 Tire int cnt son char str 字符串

image

导读 ^ _ ^

Tire树是很关键的一种数据结构,你应该听过他的另外一个名字,即字典树,可以高效存储和查找字符串集合。

何为Tire树

一种高效存储和查找字符串集合的数据结构
结尾进行标记,统计出现次数
image.png

字符串统计

表示方式

son数组

  • 第一维度用了表示节点,由idx控制
  • 第二维度用来表示当前子节点枝条,有26个字母构成

cnt数组

  • 用来统计当前节点出现的次数

关系映射

  • 将字符 - ‘a’映射成数字
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;//注意0是根节点,又是空节点
char str[N];

void insert(char str[ ]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
       int u = str[i] - 'a';
       if(!son[p][u]) son[p][u] = ++idx;//当前没有用过
       p = son[p][u];//用过了,下个儿子
    }
    cnt[p]++;//最终儿子结尾+1
}

int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;//结尾没有继续了
        p = son[p][u];//下一个儿子
    }
    return cnt[p];
}

int main( ) {
    int n;
    scanf("%d", &n);

    while(n--) {
        char op[2];//过掉一个换行
        scanf("%s%s",op,str);
        if(op[0] == 'I')insert(str);
        else printf("%d\n",query(str));
    }
    return 0;
}

#谢谢你的观看!

^ _ ^

标签:高效,Tire,int,cnt,son,char,str,字符串
From: https://www.cnblogs.com/HX-Note/p/17154855.html

相关文章

  • 牛客网算法题:给定一个字符串,计算从做到右的字符出现的个数
    题目:给定一个字符串,计算出从做到右的字符出现的个数忽略字符计算后个数为1的数字例如原始输入字符串:"​​​aabccccaaa​​​"期望输出:“​​​a2bc4a3​​”解释:从左到......
  • LQB05 数码管动态扫描,显示字符串
    1、蓝桥杯51单片机开发板的数码管是共阳数码管;需要注意段码表的推导。掌握推导段码表。2、stcisp软件的数码管代码,是共阴的模式,注意取反的话,如何实现?3、定时器动态扫描......
  • SpringBoot-使用链接字符串动态创建SqlSessionFactory执行任意SQL脚本
    SpringBoot-使用链接字符串动态创建SqlSessionFactory执行任意SQL脚本引言SpringBoot大大减少了使用XML配置的复杂性,但是想通过代码去实例化一个对象有点儿无从下手的感觉。......
  • 字符串与base64相互转换
    字符串转base64functionencode(str){//对字符串进行编码varencode=encodeURI(str);//对编码的字符串转化base64varbase64=btoa(encode);......
  • linux 命令行中 几个高效快捷键
     001、ctrl+a:将光标移动到命令行的开头,相当于键盘中的home键002、ctrl+e:将光标移动到命令行的结尾,相当于键盘中的end键003、ctrl+u:剪切光标所在位置之前的......
  • 前端小案例——拆分字符串中多个数字和文字
    1<!--*示例:2016027马红旗22*处理结果:2016027-马红旗2-->3<htmllang="en">45<head>6<metacharset="UTF-8">7<metahttp-equiv="X-UA-Co......
  • T-SQL——将字符串转为单列
    目录0.背景1.使用STRING_SPLIT函数2.自定义分裂函数3.使用示例shanzm-2023年2月22日0.背景代码中执行存储过程,参数是多个且不确定数量,期望SQL查询时使用该参数作......
  • 求字符串中最长长度的字串
    题目给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。今天做题时间有点晚,之前学习算法与数据结构,解决方法好像是用kmp算法来着,今天想发一......
  • 【LeeCode】1208. 尽可能使字符串相等
    【题目描述】给你两个长度相同的字符串,​​s​​​ 和 ​​t​​。将 ​​s​​ 中的第 ​​i​​ 个字符变到 ​​t​​ 中的第 ​​i​​ 个字符需要 ​​|s[i......
  • Redis设计与实现—简单动态字符串、链表、字典
    前言《Redis设计与实现》数据结构部分有关字符串类型介绍。@目录前言一、数据结构——简单动态字符串1.1SDS定义1.2SDS与C字符串的区别1.2.1常数复杂度获取字符串长度......