kmp 算法简介及 next 数组推导

Max 的个人博客 / 3390 / 1 / 创建于 5年前 / 更新于 5年前

Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

比如下面这种情况

gif中可以看出，匹配失败之后kmp算法不对主字符串的指针进行任何的回退，其关心的是对搜索词指针的处理。

细心的你可能已经感受到了一点，上面的处理是抽象的（通用的），既完全不需要知道主字符串具体是多少的情况下进行的模拟演习。

gif中模拟了指针k在字符c处失配的情况，通过这样一个预处理，在实际匹配中，如果遇到了这种情况，我们只需要从容的将搜索词指针移动到E处，然后继续匹配即可。

补充一下，为什么搜索词在移动到 K = E的位置停了下来？
这里可以感性的理解，由于在移动过程中 AB成功进行了匹配，而在不知道 ‘?’所代表的具体字符是多少的情况下继续向前移动搜索词，则可能会出现错失匹配的情况。

现在依旧已ABEABC作为搜索词，再看几种演习情况

我们来总结一下规律。
对于前两种情况K指针都没有移动到起点0，而是中途位置停了下来。
可以发现 ABEAB?与ABEABC在失配字符之前的字符ABEAB 的头部与尾部存在相同的字符AB。

ABEA?和ABEAB在失配之前的字符ABEA中，头部和尾部存在相同的字符 A。

对于这种字符我们称之为前后缀，通过上面的图我们发现K指针在失配时移动到的位置刚好是前缀的后一个字符。但一个字符串的前缀并不是唯一的，所以这句话非常不严谨。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

出自阮一峰字符串匹配的KMP算法

了解了前缀与后缀之后，我们再次定义。
当指针j所指向的字符与指针k所指向的字符失配时，失配之前的字符存在一个前缀集合和一个后缀集合，我们可以得到

k' = max(0 ~ k-1的前缀集合 ∩ 0 ~ k-1的后缀集合后缀集合)

k'的含义从公式中看的很清楚（前缀与后缀的交集的最大值）。而另一层含义则是，如果搜索词下标从0开始计算，当k处失配时，我们只需要将k移动到k'处继续匹配即可。

kmp算法的通常把计算出的k'放到next数组中存储
next[k] = k'。当我们实战中在指针k处失配时,我们只需要将k指针回退到k'处，既k = k' = next[k]即可。

确实如我们之前所言，通过定义可以清楚的认识到，计算next数组完全不需要主字符串参与，完全是搜索词自匹配计算k' = max(0~k-1的前缀集合 ∩ 0~k-1的后缀集合)的过程。

这个定义虽然很严谨，便于理解，但却不能很好的使用计算机语言描述出来。下面看看便于计算机理解的next数组的推导过程。这应该是整个kmp算法最难理解的地方

next数组推导

根据next数组的定义,我们可以有

若 next[j] = k，则 w[0 ~ k-1] = w[j-k ~ j-1]

要明白这两者之间是充分必要条件关系，既
若 w[0 ~ k-1] = w[j-k ~ j-1]则next[j] = k

下图图中的情况为一种满足定义的情况next[6] = 2

这个我不知道怎么证明，因为这是由next数组的定义得到的，所以也不需要证明。

现在已经知道了next[j] = k，顺理成章，接下来我们继续求next[j+1]，next[j+1]求解过程中存在两种情况

w[k] == w[j]

根据上面的推导，当 w[k] == w[j]时，有w[0 ~ k] = w[j-k ~ j]，则可以得到 next[j+1] = k + 1

w[k] != w[j]

若w[k] != w[j]则进入了熟悉的字符串失配环节，明确一下，谁与谁的比较中产生了失配？下图是一个符合我们讨论的例子

可以看出在寻找字符串ABEFABA的最大前后缀交集时，k与j发生了失配

在kmp算法中如果发生了这种情况，则另 k = next[k]，然后再次让w[k]与w[j]比较。那么问题来了

为什么当w[k] != w[j]时,令 k = next[k], 而不是k = k-1或者其他呢?

w[k]与w[j]失配时， k至少要移动到next[k]处才能使得k与主字符串的j继续匹配。这是next数组的定义，现在只不过在使用这个定义而已
w[k] != w[j]，所以另k' = next[k]，假如此时w[k'] == w[j]，如何证明 w[0 ~ k'] == w[j-k' ~ j] 呢?(图中粉色部分)

由k' = next[k]得到w[0 ~ k'-1] == w[k-k' ~ k-1]

由next[j] = k得到w[0 ~ k-1] == w[j-k ~ j-1]

因为 w[0 ~ k-1] == w[j-k ~ j-1]
所以 w[k-k' ~ k-1] == w[j-k' ~ j-1]

这里属于感性证明，能力不足暂时无法使用公式证明

所以 w[0 ~ k'-1] == w[j-k' ~ j-1]

又因为 w[k'] == w[j]
所以 w[0 ~ k'] == w[j-k' ~ j]

由 w[0 ~ k'] == w[j-k' ~ j]，得到 next[j+1] = k' + 1

这是假如此时 w[k'] == w[j]的情况，但大多数情况是w[k'] != w[j]的，这种情况我们在算法实现中讨论。

算法实现

next数组实现

private function getNext($word): array
{
    $next = [-1];
    $len = strlen($word);
    $k = -1;
    $j = 0;

    while ($j < $len - 1) {
        if ($k == -1 || $word[$j] == $word[$k]) {
            $next[++$j] = ++$k;
        } else {
            $k = $next[$k];
        }
    }

    return $next;
}

next[0] = -1 中-1是一种特殊标志，方便进行判断。在上面的w[k] != w[j]时，我们另 k = next[k]然后再去判断w[k]是否等于w[j]，如果还是不相等，则再另k = next[k]像这样一直循环下去。
但是循环总归有个尽头，在尽头会出现这种情况，此时k = 0，w[k] != w[j]，按照算法k = next[0] = -1。

因此当我们看到 k = -1时，我们就能够知道 w[0 ~ k]不存在前缀与后缀的交集，既 max(0~k的前缀集合 ∩ 0~k的后缀集合) = 0 所以我们另 next[k+1] = 0即可

上面的算法为了保持简洁性，令特殊值为-1，使得一个if，else可以覆盖三种情况，当然你用下面的写法也是一个意思

if($k == -1) {
    $next[++$j] = 0;
} elseif ($word[$j] == $word[$k]) {
    $next[++$j] = ++$k;
} else {
    $k = $next[$k];
}

详细实现含测试用例
https://github.com/weiwenhao/algorithm/blo...

结

kmp算法实际上在字符串匹配中使用的情况并不多，虽然其时间复杂度是O(m+n)，但实际上其表现跟朴素算法并不会差太多，在学习的过程中其实也应该发现了，能够部分匹配的情况其实不多见。
不得不说kmp算法非常的难以理解，细节太多很容易陷入一个拆东墙补西墙的情况，各种牛角尖钻到停不下来。但是其状态机的思想，以及next数组的推导过程却非常值得学习。