数据结构（邓俊辉）学习笔记】串 03——KMP算法：记忆法

1. 重复匹配的前缀

关于串匹配，包括蛮力算法在内，至少有30多种知名的算法，而接下来，就将介绍其中最为经典的 KMP 算法。这个算法之所以著名，不仅是由于它出自包括 Knuth 在内的若干名人之手，而更重要的是，它正如我们此前所期盼的那样，能够保证即便在最坏的情况下，运行时间也不超过线性O(n)。

当然，在这一部分的末尾，我们也将通过对比指出，这一算法从某种意义上讲，也是被过度地神化了。

正所谓不破不立，我们的 KMP 之旅，是起始于蛮力算法。首先来揭示，蛮力算法为什么会如此低效。

从宏观上来看，蛮力算法的一次典型运行过程，可以由这样一幅图来示意。假定这就是足够长的一个文本串，而下面则是相对而言更短的模式串。我们知道，在算法的每一步迭代中，相对于文本串，模式串都有一个相应的对齐位置。

请注意，在这个算法中，相邻的对齐位置之间，间隔都是一个字符。在每一对齐位置，这个算法都需要从首字符开始，进行一系列的比对，直至在某个位置发生失配。请注意，在此之前每一次迭代所花费的时间都正比于这样一个前缀。

在这个图中，我们可以清晰地看到，所有这些前缀之间存在着大量的重复。也就是说在此前曾经参与比对的字符，在后续的迭代中，往往还会再次地参与比对。如果我们将视线集中于文本串中的某一特定字符，就会发现，在最坏情况下，它有可能会与模式串中的每一个字符都比较一次。也就是说，文本串中的每一个字符，都有可能参与多达 M 次的比对。

依然回到我们上一节末尾，针对蛮力算法所给的那个最坏实例。我们可以从这样一个新的角度来阐释，为什么蛮力算法效率如此低下。因为站在文本串中每一个字符的角度来看，在这种最坏情况下，它都会与模式串中的每一个字符比对一次。

在这类这坏情况下，每一步迭代都需要经过长途跋涉，才能够在最后一个位置发现失配。因此，反过来，这类情况之所以棘手，也可以理解为在模式串中存在大量与文本串能够局部匹配的前缀，而蛮力算法的计算成本，也主要消耗于这些前缀中。

然而，在对这个具体的实例进一步观察之后，我们或许会发现，这些局部匹配前缀所涉及的比对，绝大多数都是不必进行的，至少不必反复进行。能看出其中的原因吗？

2. 不变性

应该记得，我们在分析蛮力算法时，曾经指出过这个算法的一个不变性。没错，不变性。整个算法过程中的任何一个时刻，都可以表示为这样一幅具有一般意义的插图。是的，在当前假设我们需要对 T[i] 和 P[j] 进行比对，并且根据比对的结果，来确定算法的下一步走向。

而这里所蕴含的不变性就是，这个子串与这个前缀完全相等。是的，子串与前缀完全相等。这意味着什么呢？是的，这意味着我们已经完全掌握了这个子串的全部信息。也就说它具体是由哪些字符所构成的，而这类信息完全可以为后续的各步比对所利用。

还是回到我们刚才的那个例子，考察在当前这步迭代中的最后一次比对，也就是那次失败的比对，正如我们的不变性所指出的，尽管这次比对是失败的，但它却意味着在此前我们已经获得过足够多次成功的比对。就这个例子而言，也就是一系列的0-0匹配。没错，0-0匹配。

这一点其实可以概括为一条非常有用的信息。具体来说也就是，在主串中对应的这个子串完全是由0构成的。没错，在这种情况下，与模式串前缀所对应的文本串的子串完全是由0构成的。

很可惜，此前的蛮力算法没有注意到并且充分利用这一点。事实上，它会正规中矩地将模式串右移一个字符，然后试图重新与这个子串进行匹配。现在应该不难理解，实际上，既然无论是这个字串还是这个前缀，都是完全由0所构成的，所以它们的任何局部比对都必然会整体成功。

这意味着，至少在当前的这种情况下，这个子串与这个模式串的任何比对，都会以完全匹配而返回。尽管它们的第一次比对的确有必要，但如果像蛮力算法那样，在此后还反复地将它们进行比对，就显然是没有必要的。

3. 记忆力

事实上，只要我们记忆力足够强，自然也就可以将在前一轮比对中所获得的上述信息存储起来，并为后续的比对所利用。

而这类信息的使用原理与方法则可以由上图来表示。请再次确认这个图所对应的场景：也就是在当前的对齐位置，我们首次在 T[i] 和 P[j] 处发生了一次失配。而反过来，P[j]所对应的那个前缀以及 T[i] 所对应的那个子串是完全匹配的。

只要我们能够充分地利用这类信息，就可以迅速地排除掉大量的对齐位置，从而令模式串得以迅速地、大幅度地向后滑动。

而且同样是利用这类信息，我们甚至可以不必去重复比对在 T[i] 之前的任何字符。也就是说在模式串的下一对齐位置，新一轮的比对只需从 T[i]与新的 P[j]开始。

4. 预知力

依然回到我们已经多次使用的这个二进制串的实例，根据刚才的分析，在当前这轮比对失败于模式串的末字符之后，即便我们依然只能向后移动一个字符，但相对于新的 P[j] 而言，整个前缀都无需重复比对了。

也就是说，我们只需从上一次失败的位置出发，继续进行下一轮的比对。正所谓从哪里跌倒的就从哪里爬起来。实际上，即便是对于更为复杂的例子，也依然存在此类优化的可能。

比如这就是一例，其模式与刚才类似。也就是说，相对于当前这个对齐位置，我们所做的一轮比对首次失败于 e 和 o 之间的失配。请注意，在这种情况下，我们完全不必亦步亦趋的右移模式串，而是可以大胆地将它后移三个字符，也就是说此前的两个对齐位置都可以排除掉。

你能看出这背后的原因吗？没错。如果一个位置值得对齐。那么它的一个必要条件就是，所对应的首字符应该与模式串的首字符一样，也是 R。在这种情况下，无论E或G 都不是 R 。

这里我们再强调一次，关于这个子串的所有信息，都是我们通过前一轮的比对所获得的。而通过这两个实例，我们已经切实地看到，只要我们能够对这类信息充分加以利用，就可以获得两个方面的优化效果。

1. 一方面，我们可能大幅度地向后滑动模式串；

2. 而另一方面，我们也可避免大量重复的比对。

   而为了同时兑现这两个方面的优化，我们算法实际上只需具有某一种预知力即可。具体来说也就是，在每一次失败之后，我们应该将模式传中的哪一个字符与文本串中刚才失败的那个字符，彼此重新对齐，并继续从这个位置开始进行比对。在这个例子中也就是要确定这个0，而在这个例子中，相应的对齐位置也就是这个 E。

那么具体地，又当如何来确定此类继任字符的位置呢？为此我们需要花费多少时间和空间？而且更重要地，既然是作为预知力，我们的算法，能否在事先就提前确定此类继任字符的位置呢？好消息是，所有这些都是可能的。