极客讲堂 - 数据结构与算法之美 - 深度和广度优先搜索,字符串匹配基础,Trie树,AC自动机,贪心算法,分治算法

2023-11-05

31 | 深度和广度优先搜索

1. 基于数据结构“图”的搜索算法,比较简单的有 深度优先 和 广度优先 搜索算法。适用于图不大的情况。

2. 广度优先用 队列 来实现。逐层遍历,每遍历一个结点,就放入队列。 

3. 深度优先用 栈 来实现。通过堆栈,一层一层递归下去。

4. 深度优先和广度优先搜索的时间复杂度都是 O(E),空间复杂度是 O(V)。

    E: 图结构里的边的数目。

    V: 图结构里的结点的数目。

 

32 | 字符串匹配基础(上)

1. 定义: 在字符串 A 中查找字符串 B,那字符串 A 就是主串,字符串B 就是模式串。

2. 字符串匹配算法,比较简单粗暴的方法是 BF 算法。 方式是:逐个逐个字母地比较主串和模式串。

    理论上的最坏情况,时间复杂度是 O(n*m)。 n: 主串长度;m: 模式串长度。

3. RK 算法效率要高不少。方式是:

(1) 求主串中每个子串的hash值,和模式串的hash值做比较。数字之间比较是非常快速的,所以模式串和子串比较的

效率就提高了。

(2) 计算hash值时,可以把字符串视为一个26进制数(26个英文字母),然后转成十进制数。这就能快速计算出hash值。

     而且,下一个子串的是可以根据上一子串的数值来快速计算出结果(有一个公式),不需要每个子串都完整算一次hash值。

     通过查表法,还能进一步提升计算hash值的效率。

     hash值相同的话,子串和匹配串就相等了。

(3) 这个方式要注意,这个26进制数转成10进制数时ÿ

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

极客讲堂 - 数据结构与算法之美 - 深度和广度优先搜索,字符串匹配基础,Trie树,AC自动机,贪心算法,分治算法 的相关文章

随机推荐

  • go-zero jwt 鉴权快速实战

    前面我们分享了 go zero 的快速实战以及日志组件的剖析 本次我们来实战使用 go zero jwt 鉴权 本次文章主要是分享关于 go zero 中 jwt 的使用方式 会以一个 demo 的方式来进行实战 对于使用 goctl 工具
  • 【QNX】快速入门指南

    目录 1 QNX 快速入门指南 2 系统要求 2 安装 QNX Momentics 开发套件 3 安装 QNX Neutrino 实时操作系统 4 QNX Neutrino 操作系统的联网 1 QNX 快速入门指南 本指南旨在帮助用户安装和
  • 基于24位AD转换模块HX711的重量称量实验(已补充皮重存储,线性温度漂移修正)...

    转载 http www geek workshop com thread 2315 1 1 html 以前在X宝上买过一个称重放大器 180 大洋 原理基本上就是把桥式拉力传感器输出的mV级信号放大到5V供单片机读取 连接实验电路的时候很完
  • 猴子-从零开始学数据分析,什么程度可以找工作?

    转行到数据行业差不多一个月了 才敢来回答这个问题 其中各种心酸 无助真不是能用语言能表达的 下面我尽可能的详细的说说 希望对接下来想转行的朋友有帮助 我是2016年6月毕业的控制工程硕士 就是个不入流的普通二本 学习成绩也不好 糊里糊涂的也
  • 计算机中文件夹怎么上密码,文件夹怎么设置密码,详细教您如何给电脑上文件夹设置密码...

    在平常的工作中 有时候我们为了保证信息的安全性总是喜欢建立一个文件夹然后进行加密 虽然这一操作很容易 但是对于普通用户来说却是不简单 那么文件夹该怎么加密码呢 下面 小编就来跟大家分享文件夹设置密码的操作技巧 众所周知 在工作时 难免会涉及
  • [需求管理-10]:功能规范内容与撰写流程

    目录 第1章 需求规格说明书与功能规范的异同 第2章 功能规范撰写的总体流程 2 1 什么是功能规范撰写的流程 2 2 功能规范撰写流程的职责 2 3 什么时候启动功能规范CFAM撰写流程 2 4 哪些人参与功能规范撰写流程 2 5 项目相
  • Java中有指针么?

    指针的概念对于没有学过C语言的朋友是很陌生的 因为JAVA中没有学过指针 那么什么是指针呢 指针 Pointer 是编程语言中的一个对象 利用地址 它的值直接指向 Pointed to 存在电脑存储器中另一个地方的值 也就是通过地址可以找到
  • 一文清晰讲明白DDD(领域驱动设计)的知识点

    什么是DDD DDD 领域驱动设计 是一种处理高度复杂领域的设计思想 是一种架构设计方法论 是一种设计模式 以高内聚低耦合为目的 把一个复杂的软件应用系统中各个部分进行一个很好的拆解和封装 对软件系统进行模块化的一种思想 DDD不仅可以用于
  • HarmonyOS开发详解(四)——鸿蒙Page Ability功能及UI界面开发详解

    HarmonyOS里面的界面通过Page Ability和Java UI一起来实现 讲述Page Ability就离不开Ability 在HarmonyOS里面把各种具备的能力进行抽象 叫做Ability Ability是程序重要的组成部分
  • 笔记——关于QLabel重写paintEvent有背景图绘制数据无法显示的问题

    一般重写paintEvent时都会调用基类本身的paintEvent来刷新我们的界面 在自定义QLabel时 当想给自定义Label设置背景图时 若将QLabel paintEvent放在代码块末尾 那么会导致绘制数据无法显示 解决方法将其
  • INSERT讲解

    INSERT简介 基本格式 insert into 表名 values 参数 注意 参数必须跟表里的列一一对应 insert into 表名 列明 values 参数 注意 参数必须跟 列明 一一对应 多条插入时 将多个参数插入到表1 in
  • 【FRRouting User Guide】【Basic 】(五)VTY shell

    vtysh为单个组合会话中的所有FRR守护进程提供了一个组合前端 默认情况下 它在生成时启用 但可以通过configure脚本的 disable vtysh选项禁用 vtysh有一个配置文件 vtysh conf文件 该文件的位置不能从 e
  • matlab软件 可扩展性要求,对软件设计可扩展性的思考

    通常设计软件的时候 可扩展性是一个设计的考量点 可扩展性的优点自然很多 如 增加需求的迭代速度 提高维护效率 但是最近在维护系统的过程中 发现系统设计过于复杂 导致学习成本和维护成本剧增 背后的原因是为了增加系统的可扩展性 增加软件的复杂度
  • element Ui 表格内容 自定义数量,超出隐藏...

    在使用table表格时 让单元格内的字数超出时隐藏并 可通过设置宽度 加show overflow tooltip来实现
  • matlab暑期学习笔记(1)——句柄

    matlab中的句柄等价于C语言中的指针 句柄分很多种 函数句柄 图形句柄等等 1 图形句柄 图形句柄就特指这个图形 例如 h plot x y 那么h就相当于这个图形的句柄 设置该图形时 只需要set h 即可 2 函数句柄 matlab
  • 深入浅出RPC框架

    Powered by NEFU AB IN 文章目录 深入浅出RPC框架 青训营 RPC 框架分层设计 远程函数调用 RPC 介绍 名词解释 一次RPC过程 RPC好处和弊端 分层设计 编解码层 协议层 网络通信层 RPC 关键指标分析与企
  • volatile的原理和实现机制 系统级别原理 MESI协议 总结笔记

    https blog csdn net jjavaboy article details 77164474 http www infoq com cn articles ftf java volatile volatile原理 底层是靠一个
  • phpstorm插件集合

    插件安装方法有两种 Files gt Settings gt Plugins gt browse repositories Files gt Settings gt Plugins gt Install plugin from disk 1
  • FastJson序列化后Date日期变成时间戳

    执行结果 以上可以看到productionDate通过FastJson序列化后变成时间戳 如果我们想要转换成指定格式 尝试以下方法 日期属性字段上添加 JSONField注解 JSONField format yyyy MM dd priv
  • 极客讲堂 - 数据结构与算法之美 - 深度和广度优先搜索,字符串匹配基础,Trie树,AC自动机,贪心算法,分治算法

    31 深度和广度优先搜索 1 基于数据结构 图 的搜索算法 比较简单的有 深度优先 和 广度优先 搜索算法 适用于图不大的情况 2 广度优先用 队列 来实现 逐层遍历 每遍历一个结点 就放入队列 3 深度优先用 栈 来实现 通过堆栈 一层一