最近赶项目进度,几乎没什么精力学习研究了,但是就算加班也不能阻止我发文!

前言

KMP算法是什么,为什么叫这个名字,我就不再重复了,反正网上一搜一大把。原理也一搜一大把。

不过不管是好文章还是滥竽充数(指CSDN)的文章,我看了之后都感觉无法完全理解。为什么要自匹配?为什么next[0]是-1?为什么有的kmp算法开头是0有的是-1?有的作者觉得设为-1是理所当然的,就和数学定理一样。

我不知道我写的这个是不是很好理解,但是我至少说服自己可以这么理解。

关于KMP算法原理的讲解,我查了不少资料,包括公式化解释的严奶奶的《数据结构》[1]、阮一峰的《字符串匹配的KMP算法》[2],当然还有《算法导论》第32章第4节(😅虽然这本书买了挺久的但是厚厚的没怎么看)。至于Knuth等原作者的原论文我没去找。

我认为要更好理解这个算法的原理还是要靠视频演示或者说有人言传身教。因此我找来了上面这个阿三哥的视频,个人认为视频讲解中讲得比较好的(虽然不是很完全)。希望读者可以先看看这个视频有个理解。

# 实例演练

首先我们用一个例子进行手动匹配,然后使用文字总结提取出相应的规则,接着将这些规则转化为代码,就可以得到初版的kmp算法。

有如下主字符串和子字符串——

主串:

子串:

:为了便于理解,下面用区分两个字符串,并用角标表示相应字符的位置)

直观从视觉角度上看,我们可以直接看出,主串的前4个字符与子串前4个字符是匹配的(都是A1B2A3B4),只有第五个字符不同(主串是C5,子串是A5)。并且我们也知道,子A1和子B2肯定也是不同的,所以按照暴力匹配法发现不匹配时直接后移一位的操作也没有必要,主B2和子B2匹配的情况下再拿子A1去和主B2匹配没有任何意义。

那么要往后移动几位合适呢?从视觉上判断,我们知道子串中前一个A1B2和后一个A3B4是重复的,这意味着我们下一轮匹配可以直接把开头一个A1B2直接和后一个A3B4对应的主串A3B4匹配上,也就是主A3B4子A1B2。前两个字符不需要比较是否匹配,我们可以直接从子串第三位开始比较。

主串:

字串:

发现主C5和子A3不匹配。这时候我们知道因为子A1和子B2不重复,所以在前两位都匹配的情况下,后移一位没有意义,直接后移两位。又因为子串中匹配的字符没有重复,所以我们新的比较要从字串的第一位开始。

主串:

字串:

然而子A1和主C5依旧不匹配。而子B2和主A6也不匹配,这意味着子A1和主A6可能是匹配的(不要吐槽视觉上明显匹配,因为程序并不知道这两个都是A,只能通过逻辑判断),所以后移一位。

主串:

字串:

经过比较,发现主A6B7匹配子A1B2,主C8和子A3不匹配。基于同样的判断,我们再次后移两位。

主串:

字串:

主串:

字串:

匹配完成!

# 提取规则

经过上一节的手动匹配,我们可以发现,当发现子串与主串部分匹配的时候,我们都会首先关注子串不匹配的那个字符,获得它的位置(角标)。因为它是第一个不匹配的字符,所以它前面的字符肯定是匹配的。然后我们考虑子串前面匹配的字符串中,有没有重复的部分:如果没有重复,意味着在和主串匹配的情况下,往后移动一两位是没有意义的,可以直接移动整个匹配部分的长度,从头开始再匹配;如果有重复的,那么就把重复的部分直接移动过来,并且因为知道是重复,所以必然是匹配,不需要再比较,直接从重复的部分的下一个字符开始比较。

上面这段话有点长,于是我们对其进行提炼,总结出如下规则(称为规则1):

  • 逐字匹配,失配提示
  • 回溯失配前一个字符,获得与它重复的字符的位置,移动到当前位置,并对下一个字符(即失配字符)进行比较
  • 若无重复,直接把第一个字符移动到失配处,进行比较

我们发现,在进行字符串匹配的时候,与主串无关,我们主要关注子串自身的重复度,并需要记录每个字符重复程度的信息。

所以我们决定,使用一个数组记录信息。其键表示子串字符的位置,值表示当前字符失配时,与前一个匹配字符重复的字符的下一个字符的位置。因为记录的是下一个字符的位置信息,所以就称其为next数组。

下面,我们先实现获取next数组的代码。

# 获取next数组

还记得上面提出的三点规则吗?好吧,这么短的距离,应该不可能就忘了吧?为了方便代码书写,我们可以对其做一些语义转化。

忘了主串,我们现在只关注子串。

  • 用两个变量j和i,分别表示子串上一前一后两个字符的位置。其初始值是j=0和i=1
  • 如果i字符与j字符重复,next[i]记录位置j的字符的下一个字符的位置,也就是next[i] = j+1
  • 然后i和j双双后移一位字符,再次比较是否重复
  • 当i字符与j字符不重复时,如果j的位置是起始位置,那j就不动,记录next[i]为起始,i往后移动一位,比较j和i+1是否重复
  • 如果j的位置大于起始位置,那么i不动,寻找j前一位字符记录的与之重复的字符的下一位字符的位置,也就是next[j-1],然后比较与i是否重复

上面的五点规则(称为规则2),可能有人会对第二点和第四、五点的处理有疑问,下面给出解释:

why重复时i要记录j+1?

在规则1的第二点,我们知道,失配时,要做的事情就是找到子串前一个字符,获取与它重复的字符的下一个字符的位置,然后与失配主串字符比较,换言之,当i与j重复时,i+1是有可能在与主串进行匹配时发生失配,到时候根据规则1,就会寻找与i字符重复的字符的下一个字符的位置,也就是j的下一个字符的位置。所以next[i]记录的自然就是j+1。

why不重复且j=0时next[i]为0?

当j为0时,j与i不重复,意味着i之前没有任何字符和i重复,那么如果i与主串比较失配时,子串就得从开头和失配字符进行比较,所以next[i]=0,也就是起始位置

why不重复时比较next[j-1]和i?

由于规则2的第三点,我们知道,如果发生重复,那么i和j就会双双后移一个位置,也就是i++和j++。所以当j大于0且与i不重复时,说明j-1和i-1是重复的,换言之,我们可以根据规则1的第二点,j与i失配时,找到j的前一个字符,获取与它重复的字符的下一个字符的位置next[j-1],然后判断那个字符是否与i匹配。所以很自然的,我们就可以得出当j与i不重复,那就比较next[j-1]和i是否重复

细心的读者也许会发现,在提到规则1时,我用的是匹配这个词,而提到规则时,我用的是重复这个词。这两个词在这里表达完全一致的意思,之所以区别使用,是为了使读者能清晰认识到,现在讨论的是主串与子串的匹配,还是子串自身的重复性。如果在总结规则的过程中混乱了自己的判断场景,就会陷入逻辑混乱的状态。

好了,我们已经总结出获取next数组的逻辑规则,那么要将之转化为代码就变得很容易——

<?php
/**
 * @var string $string 子串
 */
function getNext($string)
{
    $j = 0; $i = 1;  // 初始化位置j和i
    $len = strlen($string);  // 获取子串长度,避免i超出长度
    $next[0] = 0;  // 因为next的键是i,而i=0时,没有j字符可以与它比较
    // 因为如果j=0,那么就相当于自己和自己比较,没有意义
    // 而next的值表示的是当前字符不重复时下一次进行比较的字符的位置,所以填入0表示从第一个字符开始比较
    // 不用担心因为是0不重复又从0开始会陷入无限循环,因为规则2的第四点已经规定了j为0时i要往后移动
    while ($i < $len) {
        if ($string[$j] == $string[i]) {  // 当i与j重复时
            $next[$i] = $j + 1;  // 当前的位置记录与之重复的字符的下一个字符的位置
            $i ++; $j ++;  // 双双向后移动一位
        } else {  // 不重复时
            if ($j == 0) {  // 如果j是0
                $next[$i] = 0;  // 规则2疑问解答第二点
                $i ++;  // i就往后移动一位
            } else {  // 如果j大于0
                $j = $next[$j-1];  // 寻找j前一位字符记录的与之重复的字符的下一位字符的位置
            }
        }
    }
    return $next;
}

运行这段代码,就可以获得子串的next数组。

到这里为止,基本都是上文的阿三哥视频的内容文字描述,以及我个人做出的一些疑点补充解释。

# next数组求法的优化

当然,如果只是将三哥的视频内容转化成文字描述,我根本没有必要如此大费周章。所以文章并不是到此为止。

上面我提到,三哥视频虽然讲得好,但是并不完全。这里的不完全,包括next的另一种表现形式,以及kmp算法本身的一些改进。

我们先来关注next的另一种表现形式的问题。

我在查找资料的过程中,常常发现,有的资料中next数组第一位是0,有的却是-1。而从上面的理解一路走来,也不会得出是-1的结果啊?后来我看到有人说,之所以是-1,是因为next数组的整体值向右进行了错位移动,使next[j+1] = next[j]。所以next[0]没了值,就定义为-1。

W-H-Y?整体右移我可以理解,但是为什么要定义next[0]是-1?为什么不能是-2?我找遍全网,所有人都是一笔带过:

“总之我们把它定义为-1就对了,因为《数据结构》就是这么说的”——无法理解的数学公式就推到规定如此就行了!

“这不是很自然的事情吗?不是0,那就定义为-1啊”——也许是我太笨,没有catch到这种解释的自然逻辑所在。

不,我不能接受这样草率的解释。这样强行下结论会给我一种吃饭噎住的感觉难以接受!因此,我决定自己找出能够接受的解释。

# 右移的原因

重新审视规则1,我们发现,第二点中,当i字符失配发生时,我们要先回溯到失配前的一个字符,然后再通过next数组获取与之重复的字符的下一个字符的位置。也就是说,i失配时,其实我们想要的是next[i-1]的值。既然如此,在失配时,next[i]对我们毫无意义,可以推论,子串的最后一个字符next[last]只对第last+1个字符有意义,而子串并没有第last+1个字符,因此next[last]无意义。

而因为失配字符处我们关心的是前一个字符的值,所以我们为何不将next数组的值整体右移,这样既除掉了无意义的next[last],又可以在失配发生时,直接通过next[i]获取到前一个字符的重复字符的下一个字符的位置。

说做就做,我们立马对getNext进行修改。这时候我们就面临一个问题,值整体右移之后,next[0]应该是什么?

# next[0]的值

这一切,可以从j和i的初始值开始说起。

在上面的next数组求法中,我们的比较是从第1位字符开始的,因此j=0而i=1。现在,我们将next的值整体右移,每个next[i]的值相当于以前的prenext[i-1]的值。这意味着next[0]=prenext[-1]。这将-1引进了我们计算的视野中。尽管第-1字符不存在,但是对我们接下来的逻辑处理会有一定的帮助。

因为引入了-1,所以子串的开头从0变成了-1,也就是说j=-1而i=0。

而根据整体右移后修改的规则1第二点,我们可以知道,next[i]记录的是prenext[i-1],也就是说next[0] = prenext[-1]。而按照旧的规则1,当j与i不重复,且j为起始位置时,next[i]就是起始位置。而现在我们的起始位置是-1,所以next[0]=prenext[-1]=-1。

# 更改后的getNext

那么,我们总览一下修改的规则3:

  • 用两个变量j和i,分别表示子串上一前一后两个字符的位置。其初始值是j=-1和i=0
  • 当j为-1时,因为没有实际字符,没有比较意义,所以跳过当前比较,直接j+1进入下一轮比较。且因为-1只有初始时会有,而初始i为0。当j+1时,i必须也+1,避免出现自己和自己比较的无意义行为
  • 如果i字符与j字符重复,next[i+1]记录位置j的字符的下一个字符的位置,也就是next[i+1] = j+1
  • 然后i和j双双后移一位字符,再次比较是否重复
  • 当i字符与j字符不重复时,那么i不动,寻找j字符记录的与之重复的字符的下一位字符的位置,也就是next[j],然后比较与i是否重复

有了文字描述的规则3,转化为代码是很容易的事——

<?php
/**
 * @var string $string 子串
 */
function getNextNew($string)
{
    $j = -1; $i = 0;
    $len = strlen($string); 
    $next[0] = -1;
    while ($i < $len - 1) {  // 求i=len-1没有意义,因为当前i轮结果是将j填入到i+1里
        if ($j==-1 || $string[$i]==$string[$j]) {
            $j++;
            $i++;
            $next[$i] = $j;
        } else {  // 不重复
            $j = $next[$j];
        }
    }
    return $next;
}

有人看完这段代码会疑惑,不是按照规则3第2点,如果j是-1,只做双双+1处理,为什么会有个next[i]=j呢?是不是应该把if里的两个条件拆开,一个没有next[i]=j呢?

事实上,我们可以看到,当j为-1时,进行+1操作后,j为0,i为1,所以next[1] = 0。而我们知道,进行右移后,next[1]=prenext[0]=0,所以有没有next[i]=j都没有影响。而为了简洁,所以我们就将两个条件合并起来表示。

到了这一步,求next数组的代码基本上已经优化完毕,这部分称为预处理。然后我们就可以进行kmp算法本体的编写了。

# kmp算法

由于我们对规则2做了优化修改,得到规则3,相应的,我们也要对规则1做出一定的修改,使之适配规则3:

  • 逐字匹配,失配提示
  • 如果子串第一个字符就失配,那就将主串向后移动一个位置
  • 否则,获得失配字符的next值即位置,将该位置移动到失配处,进行比较
  • 若无重复,直接把第一个字符移动到失配处,进行比较
  • 如果整个子串都匹配,则返回当前匹配的主串字符位置-(子串长度-1),即匹配成功的起始位置
  • 如果匹配到最后一个位置也没有完全匹配就返回false

除了修改,我们还对规则4进行了扩充,考虑了完全匹配/不匹配以及首字失配的处理逻辑。

然后我们对照这个规则4进行代码编写——

/**
 * @var string $str 主串
 * @var string $substr 子串
 */
function kmpStrSearch($str, $substr)
{
    $next = getNextNew($substr);
    $count = strlen($str);
    $subCount = strlen($substr);
    $i = 0; $j = 0;
    while ($i < $count) {
        if ($str[$i] != $substr[$j]) {
            if ($j == 0) {
                $i ++;
            } else {
                $j = $next[$j];
            }
        } else if ($j == ($subCount-1)) {
            return $i - $subCount + 1;
        } else {
            $i ++;
            $j ++;
        }
    }
    return false;
}

运行本段代码,即可实现kmp算法的字符串匹配。

这样就完了吗?当然不是,这段代码还有可以优化改进的地方。

# getNext·二改

我们注意到,上文中

主串:

子串:

字符串在主C5和子A5失配时,子串在下一步会进行主C5和子A3的对比。

我们一眼就可以看出来,因为子A5和子A3重复,所以,这一次匹配必然也会失败,其实完全没必要进行对比,可以直接进入下一轮对比。

因此我们可以对代码做出修改,在获取下一次匹配的子串字符位置后,和之前的失配子串字符对比,是否重复,如果重复,就直接进入下一轮比较。

上面这句话的逻辑,可以在kmpStrSearch中实现,也可以在getNext中实现。本着不修改kmpStrSearch这个大方法的前提,我们把修改放在getNext中——

<?php
/**
 * @var string $string 子串
 */
function getNextHyper($string)
{
    $j = -1; $i = 0;
    $len = strlen($string); 
    $next[0] = -1;
    while ($i < $len - 1) {
        if ($j==-1 || $string[$i]==$string[$j]) {
            if ($string[++$i] == $string[++$j]) {  // 对下一个字符进行是否重复的判断
                // 如果是,那么直接获得重复的字符记录的下一个字符的位置
                $next[$i] = $next[$j];
            } else {
                $next[$i] = $j;
            }
        } else {
            $j = $next[$j];
        }
    }
    return $next;
}

# 最终成品

<?php
/**
 * @var string $string 子串
 */
function getNext($string)
{
    $j = -1; $i = 0;
    $len = strlen($string); 
    $next[0] = -1;
    while ($i < $len - 1) {
        if ($j==-1 || $string[$i]==$string[$j]) {
            if ($string[++$i] == $string[++$j]) {  // 对下一个字符进行是否重复的判断
                // 如果是,那么直接获得重复的字符记录的下一个字符的位置
                $next[$i] = $next[$j];
            } else {
                $next[$i] = $j;
            }
        } else {
            $j = $next[$j];
        }
    }
    return $next;
}
/**
 * @var string $str 主串
 * @var string $substr 子串
 */
function kmpStrSearch($str, $substr)
{
    $next = getNext($substr);
    $count = strlen($str);
    $subCount = strlen($substr);
    $i = 0; $j = 0;
    while (($i < $count) && ($j<$subCount)) {
        if ($j==-1 || $str[$i]==$substr[$j]) {
            $j ++; $i ++;
        } else {
            $j = $next[$j];
        }
    }
    if ($j == $subCount) {
        return $i - $j;
    }
    return false;
}