专栏首页C语言入门到精通数据结构 | 每日一练(107)

数据结构 | 每日一练(107)

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1.设主串 S=‘xxyxxxyxxxxyxyx’,模式串 T=‘xxyxy’。请问:如何用最少的比较次数找到 T 在 S 中出现的位置?相应的比较次数是多少?

2.KMP 算法(字符串匹配算法)较 Brute(朴素的字符串匹配)算法有哪些改进?

正确答案

PS:||代表注释

1.朴素的模式匹配(Brute-Force)时间复杂度是O(m*n),KMP算法有一定改进,时间复杂度达到O(m+n)。本题也可采用从后面匹配的方法,即从右向左扫描,比较6次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移;若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。按这种方法,本题比较18次成功。

2.KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时,KMP算法的优点更为突出.

本文分享自微信公众号 - C语言入门到精通(yclzl960229)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-03

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • OpenCV基于标记控制的分水岭分割算法演示

    图像分水岭分割是基于图像形态学的语义分割算法,常见的算法实现主要基于标记的分水岭分割方法,图示如下:

    OpenCV学堂
  • Spring Boot + Spring Cloud 实现权限管理系统 后端篇(四):集成 MyBatis 框架

    Spring Boot对于MyBatis的支持需要引入mybatis-spring-boot-starter的pom文件。

    朝雨忆轻尘
  • 如何快速找到并验证影响因变量Y的自变量X呢?

    声明:本文讨论主题的不是严谨意义上的“因果关系”,而是探讨自变量与因变量的关系(实际上不是真的因果关系),主要关注点在于找到并验证影响(或预测)因变量Y的自变量...

    1480
  • 学界 | 如何得到稳定可靠的强化学习算法?微软两篇顶会论文带来安全的平滑演进

    AI 科技评论按:强化学习最常见的应用是学习如何做出一系列决策,比如,如何一步步攀登上三千英尺高的岩壁。有机会用到强化学习并做出高水准结果的领域包括机器人(以及...

    AI研习社
  • JAVA多线程之线程间的通信方式

    本总结我对于JAVA多线程中线程之间的通信方式的理解,主要以代码结合文字的方式来讨论线程间的通信,故摘抄了书中的一些示例代码。

    哲洛不闹
  • 算法数据结构中有哪些奇技淫巧?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 巧用R语言实现各种常用的数据输入与输出

    将数据输入或加载到R工作空间中,是使用R进行数据分析的第一步。R语言支持读取众多格式的数据文件,excel文件,csv文件,txt文件和数据库(MYSQL数据库...

    1480
  • 一条命通关,这个AI算法玩超级马里奥操作秀翻天丨视频+开源代码

    从1-1到7-1,只要一条命,就能全部通过,而且操作几乎没有迟疑,如行云流水一般。

    AI算法与图像处理
  • 从 Promise 对象讲解事件循环机制

    我们知道 ES6 出现之后,事件循环机制和之前的就有些不同,这篇文章会讲这些不同的地方讲清楚。

    小生方勤

扫码关注云+社区

领取腾讯云代金券