李哥发布的文章

字符串匹配3：KMP算法

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

BM（Boyer-Moore）算法，是一种高效的单模式串匹配算法。高效的字符串匹配算法在文本编辑器这样的软件上应用是否广泛。BM算法比著名的KMP算法更加高效。

字符串匹配可分为单模式串匹配和多模式串匹配，单模式串匹配就是一个串和一个子串匹配，多模式串匹配可以一个串同时查找多个字串。

堆非常适合用来实现优先队列。优先队列每次取出都是优先级最高的元素，十分契合堆的性质。

堆分为大顶堆和小顶堆，堆是一颗完全二叉树。

规定如下：

第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。