快速手算 KMP 算法中模式串的对应数组

快速手算 KMP 算法中模式串的对应数组

概述

在数据结构与算法中，字符串的匹配一定是绕不开的一个话题。除了简单直观的暴力匹配外，字符串的模式匹配更是重点 —— 以 KMP 为代表的模式匹配算法可以将匹配时间复杂度从 $ O(mn) $ 缩短至 $ O(m+n) $，其中 $ m $ 与 $ n $ 分别是模式串与待匹配字符串的数据规模。本文将从应试计算的角度出发，用较短的篇幅与各位分享如何快速计算 KMP 算法中模式串的 next[] 数组与改进后的 nextval[] 数组。由于串的匹配是数据结构课程的必修内容，因此笔者将假定您已经初步了解什么是串的模式匹配，并且清楚为什么要使用 KMP 算法以及 next[] 与 nextval[] 数组的含义，笔者接下来只会简单地介绍一下 next[] 与 nextval[] 数组。

快速手算 next[] 数组

next[] 数组中的每个元素用于指示当模式串与主字符串（简称主串）在当前位置发生失配的时候，模式串“指针”接下来应当指向哪一个位置来重新进行匹配。如下面的表格所示，模式串 "bcbc" 的 next[] 数组中各个元素分别为 0、1、1 与 2，比如当模式串中的第二个 'b' 与主串中的某一位失配以后，模式串的“指针”将回到 1 位置，也就是对应第一个 b。请注意，笔者在此处使用了从 1 开始的下标，这将与一部分数据结构课本以及计算机学科专业基础综合考试大纲中使用的规则相同，并非机算或代码实现中的下标规则。

那么如何快速手算 next[] 数组呢？可以拆成这两个部分：

next[] 数组的前两位

对于 next[] 数组的第 1 位和第 2 位，“无脑”填 0 与 1：0 代表着如果连第 1 位都不匹配，就拿模式串的第 1 位去比较主串中的下一位；而 1 则代表了若第 2 位不匹配，则令模式串“指针”回到第 1 位的位置重新进行比较，也就是转化成上述比较第 1 位的情况。

第 3 位及以后

对于第 3 位及以后，情况就开始变得有一点点不一样了。由于我们知道，若能比较到第 $ i $ 位，则代表第 $ i-1 $ 位及以前都是匹配的。因此，记住这个规则：观察模式串在逻辑上相较于自己向右推进最少多少位之后，当前位置前面的部分还能与原模式串的当前位左边的后缀相匹配，此时当前位置上的模式串元素在原模式串上的位置就是 next[] 数组中当前位的值。这句话看起来很抽象，但实践起来非常简单，让我们继续来看 "bcbc" 的例子：

要求 next[] 数组第三位的值，我们先来观察 b 的左边部分 bc，然后相对于模式串自身推进一下看看是否还能与 bc 的子串相匹配：

推进 2 位以后，发现模式串的第 1 位已经被推到了当前位置上，第 3 位左边部分已经为空，空串自然是任何字符串的后缀，因此接下来将比较模式串的第 1 位，故 next[] 数组的对应位置填 1。

那第 4 位呢，我们同样继续来推进看看：

很幸运，这回在推进了 2 位后，一个 b 成功匹配到了 bcb 中到最后一个 b，也就是最少推进 2 位后就能原模式串左边部分的后缀产生了匹配。此时，我们观察到 c 落在了当前位置上，而这个 c 是原来模式串中的第 2 位，因此 next[] 数组的第 4 位填入数字 2：

不难发现，next[] 数组元素值的计算不依赖于主串，仅与模式串的特性相关。

Try Again

按照上述的方法，再来看一个模式串 "acbacd" 的快速计算。下面是 "acbacd" 相对于自身的推进情况：

逐位计算便可以得到：

这是为什么呢，以下是逐位分析：

• 首先第 1 位与第 2 位先填入 0 和 1；

• 第 3 位由于 a 没法与 c 匹配，故推进到底，使得左边部分为空，即推进 2 位的情况，此时 next[] 对应位填 1；

• 第 4 位由于前面 ac 与 cb 不匹配，a 也与 b 不匹配，故依然推进到底，即推进 3 位对应的情况，next[] 对应位仍填 1；

• 第 5 位则情况出现了转机，虽然 acb 与 cba 不匹配，ac 与 ba 不匹配，但有一个 a 产生了匹配，因此推进 3 位即可，此时第 5 位上的 c 在原模式串的第 2 位，则 next[] 对应位填 2；

• 第 6 位也是如此，虽然最开始推进时都没有匹配，但很快发现有一个 ac 产生了匹配，即推进 3 位时对应的情况，此时第 6 位上的 b 在原模式串的第 3 位，则 next[] 对应位填 3。

至此，您已经了解了如何快速手算 next[] 数组，并应用在不会出很长的主串与模式串作为题目的应试考试中。手算 next[] 数组是重要的基石，它为后面快速手算 nextval[] 数组提供了一个便捷的入口。

快速手算 nextval[] 数组

nextval[] 在名字上和 next[] 数组就相差了一个 “val”，说明它们的获得方式以及表示的意义应当相差不大。没错，nextval[] 数组与 next[] 数组一样，都是指示模式串的“指针”在当前位置发生失配时接下来要跳到的位置，但是基于 nextval[] 数组实现的 KMP 算法却是基于 next[] 数组的实现的加速版本。它是怎么做到加速的呢？答案就是：跳过当前位置上相同的字符比较，依据“上一次”在这里失配以后的行为直接“一步到位”跳转。

还是先回到前面的 "bcbc" 模式串的例子中。不难发现，当匹配到第 3 位时，若发生失配，模式串按理来说最终应该推进 2 位，即模式串“指针”将指向第 1 个模式串字符的位置。但此时遇到了一个问题：本来模式串第 3 位就是字符 b 了，而模式串接下来又拿一个 b 与当前位置比较 —— 这重复了一次无意义的比较。

那么应该怎么减少这样无意义的比较呢？一个很暴力的方法就是：若模式串“指针”跳转后，发现接下来要比较的字符与刚才失配时的字符相同，则按照跳转后的字符对应的 next[] 数组值再跳转一次，跳过重复的比较。这看起来有点绕，那就以这个 b 为例来看看这是怎么一回事：模式串最终推进了 2 位，下一次比较的模式串是第 1 位的 b；但可惜本来就是因为当前位置不是 b 才导致发生了失配，注意到第 1 位的 b 在失配的时候会直接“过掉”，也就是去比较主串的下一位了，为了避免重复比较一次，直接照搬第 1 位的 b 的跳转方式再推进 1 位，相当于一次性推进 $ 2+1=3 $ 位，这样就不会出现重复的比较了。

怎么样，这是不是比原来快了一些，毕竟原来是 b(3) -> b(1) -> 比较主串的下一位，现在是 b(3) -> 比较主串的下一位，一步到位、跳过了原本多余的比较。那原本第 4 位的 c 又会有什么样的表现呢？在原本的跳转中，若第 4 位失配，则模式串推进 2 位，接下来从模式串的第 2 位开始比较。

但第 2 位又是 c，自然，直接学习第 2 位的 c 是怎么推进的 —— 向右推进 1 位，让第 1 位的 b 去比较 —— next[2] 是 1。

综上，不难看出，如果每次跳转后，新参与比较的模式串的字符和上一个在这个位置失配时的模式串字符一样，那就直接将其 next[] 数组的值拿来当作自己的数组元素值，而通过这样子逐位推演、重算后的数组就是的 nextval[] 数组。

既然 nextval[] 数组由 next[] 数组派生而来，那就先干脆把 nextval[] 数组先初始化为与 next[] 数组相同。先令数组 nextval = next，设 j 为模式串“指针”，p 是模式串对象，从第 2 位开始逐位检查并修改，则可以总结为：

• if (p[j] == p[nextval[j]]) { nextval[j] = nextval[nextval[j]]; }
• else if (p[j] != p[nextval[j]]) { nextval[j] = nextval[j]; }

这便是“依据‘上一次’在这里失配以后的行为直接‘一步到位’跳转”这句话的含义。

Try Again

还是老规矩，按照上述的方法看看模式串 "acbacd" 的 nextval[] 数组的快速计算。先把 next[] 数组写出来：

先令数组 nextval = next = { 0, 1, 1, 1, 2, 3 }，然后逐位检查 nextval[]，发现第 4 位在跳到第 1 位后会重复比较 a，第 5 位在跳到第 2 位后会重复比较 c，其他位置都不会出现这种重复比较，因此其他位照搬，令 nextval[4] = nextval[nextval[4]]、nextval[5] = nextval[nextval[5]]，得到：

通过手工模拟，可以很容易地发现模式串与主串的比较次数比原来使用 next[] 数组时要少一些。这就是 nextval[] 数组在 KMP 算法中的妙用，核心奥义就在于消除重复的比较，并递推地传递到后面具有相同的模式串字符对应的 nextval[] 数组位上。

总结

本文介绍了在以 1 作为下标起始的规则下快速手算 KMP 模式串 next[] 与 nextval[] 数组的方法。计算 next[] 时，可将模式串相对于自身向右推进，寻找当前位置之前子串的最长相等前后缀，据此确定失配后的跳转位置。在此基础上，nextval[] 会进一步跳过失配后字符仍然相同的无效比较，并沿用已有的优化结果完成递推。掌握这两种数组的含义和推算过程，不仅有助于快速完成相关题目，也能更直观地理解 KMP 算法利用已匹配信息、避免主串指针回退的核心思想。欢迎各位在评论区分享关于 KMP、字符串匹配的相关知识与看法，这里是 Anawaert Blog，我们下期再见。