首页 > 其他分享 >老黑春季2023上课内容

老黑春季2023上课内容

时间:2023-03-03 21:57:22浏览次数:52  
标签:字符 上课 int 老黑 str 2023 字符串 节点 字典

KMP

字典树

一.什么是字典树
\(Trie\) 树,即字典树,是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间,最大限度地减少无谓的字符串比较。

\(Trie\) 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

二.字典树的性质

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

下图就是一个字典树:
三.字典树的操作

  1. 映射字符
    int getnum(char x){
    	if(x>='A'&&x<='Z')
    		return x-'A';
    	else if(x>='a'&&x<='z')
    		return x-'a'+26;
    	else
    		return x-'0'+52;
    }
    
  2. 插入字符串
    void insert(char str[]){
    	int p=0,len=strlen(str);
    	for(int i=0;i<len;i++){
    		int c=getnum(str[i]);
    		if(!t[p][c])
    			t[p][c]=++idx;
    		p=t[p][c];
    		cnt[p]++;
    	}
    }
    
  3. 查询操作
    int find(char str[]){
    	int p=0,len=strlen(str);
    	for(int i=0;i<len;i++){
    		int c=getnum(str[i]);
    		if(!t[p][c])
    			return 0;
    		p=t[p][c];
    	}
    	return cnt[p];
    }
    

标签:字符,上课,int,老黑,str,2023,字符串,节点,字典
From: https://www.cnblogs.com/kimi-learn/p/17177078.html

相关文章

  • day03(2023.3.2)
    今日份学习:1.字符char2.布尔型boolean 3.运算符算数运算符 4.赋值运算符和扩展赋值运算符 5.关系运算符 6.逻辑运算符 7.位运算 8.字符串 9.......
  • 2023年3月3日(软件工程日报)
    Application是Android的一大组件,在App运行过程中有且仅有一个Application对象贯穿整个生命周期    ......
  • 【总结】2023-03-01 Swap and Sort
    SwapandSort题意有一个\(1\dotsn\)的全排列\(p_1\dotsp_n\)。有\(m\)种操作,第\(i\)种操作可以交换\(p_{a_i}\)和\(p_{b_i}\)请问最多执行\(10^5\)次......
  • 2023-3-2 #41 轰鸣的钟声渐近
    236ABC288HANamelessCountingProblem被薄杀了!!首先很容易通过数位dp计算出长度为\(k\)异或为\(X\)的序列个数,这一部分是\(O(n^3\logV)\)的。一个递增序列......
  • 2023/3/2每日总结
    设置文本内容有两种方式:在XML文件中通过属性android:text设置文本在Java代码中调用文本视图对象的setText方法设置文本  >在Java代码中调用setTextSize方......
  • 【总结】2023-03-01 Σ[k=0..10^100]floor(X/10^k)
    Σ[k=0..10^100]floor(X/10^k)题意给定一个整数\(x\),求\(\sum\limits_{k=0}^{10^{100}}\lfloor\frac{x}{10^k}\rfloor\)。数据范围\(1\leqslantx\leqslant......
  • 每日总结2023/3/3
    今天学习了安卓连接sqlite并且进行登录注册操作main.xml文件<?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="http://schemas.android.com/apk/r......
  • 【总结】2023-03-01 Count Interval
    CountInterval题意给定\(n\)个数字\(a_1,a_2\ldotsa_n\)和一个整数\(k\),求有多少个非空子段之和为\(k\)。也就是问有多少对数\((l,r)(1\leqslantl\leqsla......
  • 实验一 20230302
    #include<stdio.h>intmain(){printf("0\n");printf("<H>\n");printf("II\n");return0;} #include<stdio.h>intmai......
  • 2022到2023
    2022年到2023年,工作内容发生了很大变化。原来在字节主要做iOS平台上的业务开发,使用Swift语言。后面新的工作内容主要做IoT相关,不再局限在移动端,而是围绕整个IoT系统。从i......