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进制数时ÿ