数据结构第二季 Day24 串（蛮力、KMP）
2021-11-05 本文已影响0人
望穿秋水小作坊
一、蛮力算法
1、什么是串？什么是前缀、真前缀、后缀、真后缀？
-
串：由若干个字符组成的有限序列。
image.png
2、查找一个模式串（Pattern）在文本串（Text）中的位置，有几种经典算法？（至少说 2 种吧）
- 蛮力算法
- KMP
image.png
3、什么是蛮力算法(Brute Force)？一句话简述？
- 以字符为单位，从左到右移动模式串，直到匹配成功
image.png
4、蛮力算法 01 的思路和实现
image.png
image.png
5、蛮力算法 02 的思路和实现
image.png
image.png
6、蛮力算法的时间复杂度如何？
- 平均时间复杂度 O(mn)
image.png
二、KMP
1、蛮力 VS KMP？先掌握 KMP 的总体思路方向很重要！
image.png
- 对比蛮力算法，KMP 的精妙之处：充分利用了此前比较过的内容，可以很聪明的跳过一些不必要的比较位置。
2、KMP - next 表的使用
- KMP 会预先根据模式串的内容生成一张 next 表（一般是个数组）
image.png
image.png
3、KMP 的核心原理（感觉有点说复杂了，后面再看吧）
image.png
4、KMP - 真前缀真后缀的最大公共子串长度？
image.png
5、KMP - 从最大公共子串表获得 next 表？
image.png
6、KMP - 主算法实现
image.png
7、KMP - 为什么是 “最大” 公共子串长度？
- 把下图理解了，基本就理解 KMP 了吧
image.png
8、KMP - next 表的构建思路？
image.png
image.png
9、next 表的不足之处？
image.png
10、next 表的优化思路？
image.png
image.png
image.png
11、KMP - 性能分析？
image.png
12、蛮力 VS KMP
image.png
三、其他串算法
1、BM 算法
image.png
image.png
image.png
image.png
image.png
2、RK 算法
image.png
3、Sunday 算法
image.png
4、总结：这些算法都干了些什么事情？
- 尽可能跳过不必要的比较
