天天看点

KMP算法(超容易理解的next数组求法)

我想,既然知道KMP算法了,自然对于其具体如何运作也是有一定的了解的,我也没必要再大费口舌讲废话,大家一定查过很多资料,但是其实也都看的一知半解,好像自己懂了但是又没有理解透,特别是next数组的求法感觉很蛋疼,那么我就来给大家解决一下这个next数组的问题吧,如果对KMP算法没有概念的同学请先去查清楚再过来看看。

先讲一下我们后续讲解的一些规范,我们next数组、以及模式串都是从数组的下标1开始储存的,注意不是0!(这样操作方便一点)

下面列出一个next数组:

模式串 A B A B A B B
j 1 2 3 4 5 6 7
next[j] 1 1 2 3 4 5

很多人可能对这个next数组的理解就是不正确的,我们来好好解释一下:

  • 第一个元素的next值,即next[1],默认是0,这是规定的,0则表示从头开始比较
  • 那么很多人会疑惑,那上面这个例子中,j=2的时候如果不匹配,不也是应该从头开始比较吗?那么为什么next[2]不是0而是1呢?
  • 好,你可能会机智地说,next[1]=0是你规定死的,而你的模式串又是从下标为1的地方保存起来的,当然next[2] = 1啦!
  • 我们知道KMP算法的匹配是通过next数组慢慢往前回复(如果匹配失败的话)的一个过程,那么经过next数组返回后,我们究竟是从哪里开始比较呢?是从返回的那一个开始,还是它的前一个,亦或是后一个?
  • 这就涉及对next数组的真正的理解了,我们来好好理一理,这个next数组到底是怎么一回事!
  • 所谓next数组的返回,其实是前面有一部分是重叠的,才能这样回退。用文字可能很难描述,我们直接拿上面的来举例。
  • j = 4的时候,这个B前面的A和第一个A是相同的,因此next[4]=2,这个2是怎么来的呢?
  • 这个2不是因为j=2的那个B,而是因为j=1的那个A,因为j=1的A和j=3的A相匹配了,因此next[4] = 1 + 1,这才等于的2。等号右边第一个1是j=1的1,第二个1是往右边走一位的1。
  • 如果够聪明的话你应该已经看懂了,不过没懂也没关系,再来举个例子,咱们看最后一个B,即​

    ​next[7]=5​

    ​​,如果你没理解透,就会疑惑,明明j=5时是A啊!可是如果你搞明白了,就会知道​

    ​next[7]=5​

    ​​,是因为​

    ​j=3~6​

    ​​的​

    ​ABAB​

    ​​和​

    ​j=1~4​

    ​​的​

    ​ABAB​

    ​匹配上了。
  • 还不明白的话,咱么可以回到​

    ​next​

    ​​数组的本质,我们在什么时候需要使用到​

    ​next​

    ​​数组呢?不正是在第​

    ​j​

    ​个位置的元素和主串的元素不匹配吗?那么我们就要会退到某个位置next[j],使得第j个位置前面的元素和第next[j]个位置前面的元素要是一样的啊!这时候我们会希望第j个位置的元素和第next[j]个位置的元素的值相同吗?不,如果相同的话那么一定、马上就会要继续查next[j]的next了,因此实际上根据这一点我们还可以对next数组进行优化,即如果第j个位置的元素和next[j]个位置的元素相等了,我们就直接让next[j] = next[next[j]],并且这么一直循环下去。当然这是一种对next数组的优化了,咱们在这里提到就行,也不细说了,能够理解的话也知道该怎么办了。

那咱们看一下代码吧、

求next数组的算法:

void getNext(Str substr, int next[])
{
    // 这个i永远只会往前走,而j会随着不匹配而逐渐等于next[j]
    int i = 1, j = 0;
    next[1] = 0;
    while(i < substr.length)
    {
        // j=0 表示当前指向的是第一个元素
        if(j==0 || substr.ch[i] == substr.ch[j])
        {
            // 前面提到过,前面的匹配,所以让后一个等于前一个的下标+1
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}      
int KMP(Str str, Str substr, int next[])
{
    int i=1, j=1;
    while(i<=str.length && j <= substr.length)
    {
        if(j==0 || str.ch[i] == substr.ch[j])
        {
            // 这个i指向主串。是不可能退后的
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    // 如果匹配成功
    if(j>substr.length) return i-substr.length;
    else return 0;
}      

继续阅读