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

讲解第4章的内容 99-113页

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

2、模式匹配BF、KMP （重点、难点）

3、矩阵的压缩存储

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

实验内容于10月13日公布

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

师说

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

1. Brute-Force算法

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

2. Boyer-Moore算法

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

3. Knuth-Morris-Pratt算法

穷举算法和 Boyer-Moore 算法在完全匹配中必然进行 len(P) 次匹配，KMP 算法充分利用 P 内部的字符串重叠，做进一步优化。

https://blog.csdn.net/weixin_43269174/article/details/90485767

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

http://www.tuicool.com/articles/e2Qbyyf