您申请加入课程:数据结构与算法(c 描述)
需要验证您的身份,请输入课程密码:
您的学号:
班级选择:
课程密码:

数据结构与算法(c 描述)-尊龙凯时官方app下载

https://www.scholat.com/course/sjjg
  • 创建者

    creator

    潘家辉
  • 活跃度

    activeness

  • 访问量

    visits

    197399

教学公告

18软工 第6周安排
[作者: 潘家辉  发布时间:2019-10-11 21:03:29  浏览次数:609次]

18软件工程《数据结构与算法》 第六周安排

讲解第4章的内容 99-113

1、字符串的定义、存储结构

2、模式匹配bfkmp (重点、难点)

3、矩阵的压缩存储

实验课会补充讲解stl中有关队列、栈的基础内容。

实验内容于1013日公布

大家可以根据自己的情况进行相应的预习

师说


模式匹配是数据结构中字符串的一种基本运算场景,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串。尽管早已可以在python下使用正则表达式或者使用其他语言的开发包可以高效而简洁地实现模式匹配,但了解相关算法背后机理亦不失其学习的意义。

1. brute-force算法

核心思想在于从 t 的第一个字符开始遍历每一个字符,依次匹配 p。是最简单,也最低效的匹配方法

2. boyer-moore算法

通过跳跃启发式算法避免大量无用的比较。每次逐字符匹配从 p 最后一个字符开始。

3. knuth-morris-pratt算法

穷举算法和 boyer-moore 算法在完全匹配中必然进行 len(p) 次匹配,kmp 算法充分利用 p 内部的字符串重叠,做进一步优化。





关于kmp算法(105-107页),如果看不明白,可以通过下面的链接从另外一种维度进行理解



相关课程

扫一扫二维码,快速加入本课程!

查看使用方法
网站地图