KMP算法小记

这里记录一下对于KMP算法中，两种求next数组的代码的理解

一、第一种

next数组表示的是，当在字符串P的j处失配时，j的下一个去处为next[j-1]
同时也就表示了字符串P在下标0到j之间的最长前后缀长度，以及最长前缀的下一个字符的下标位置

function getNext(p) {
  let next = [0], j = 0
  for (let i = 1; i < p.length; i++) {
    while (j > 0 && p[i] !== p[j]) {
      j = next[j - 1]
    }
    if (p[i] === p[j]) {
      j++
    }
    next[i] = j
  }
  return next
}
//'abcaa'
//[0,0,0,1,1]

1、初始化

按照上面的定义，因为单独一个字符没有前缀也没有后缀，最长前后缀也就是0，所以next[0]=0。在代码中，由于我们利用for循环来确定next的每一个位置对应的值，所以循环下标从1开始。j代表了当前状态下的最长公共前后缀长度，也是当前最长公共前缀的下一个字符，所以在i=1开始前应该为0

2、p[i] === p[j]时

注意：j代表的是当前最长前缀的下一个字符，也是当前状态下的最长前后缀长度（反复强调）。也就是说j的值表示：我们在p[0]到p[i-1]构成的字符串 $p^,$ 中，已经有长度为j的最长公共前后缀了，而j又指向了这个前缀的下一个字符。当p[i] === p[j]时，说明当前j所在位置的字符，和 $p^,$ 即将加在最后面的字符是一样的，也就等价于，当前的最长前缀包含了p[j]后，与加上p[i]后形成的新后缀又做到了相等。这样一来，最长前缀因为p[i]的加入就往后增加了一位，所以j++，同时next[i]也可以因此更新为新的j。
附：由于语序和代码的原因，j的更新也可以这么理解。在更新next[i]之前,next[i-1]对应的j的值是 $j_{i-1}$ ，因为p[i] === p[j]所以 $j_{i}=j_{i-1}+1$ ，同时j也应该指向更新后的新前缀，所以j++。
因此更容易理解的代码应该是这样

 if (p[i] === p[j]) {
      next[i] = j+1//更新next
      j++//指向最长前缀的指针向后移动
    }
  }

3、p[i] !== p[j]

这一部分可太难了。
在这里直接给出我的理解吧。
getNext这个函数本身又是一种KMP算法 。
如何理解这句话呢？
以aabcaaf为例，当i指向末尾i=6时，j指向字符b,j=2，此时p[i] !== p[j]。这可以看作是aab和aaf的失配，所以简单一句话就是getNext也是在做p[0]到p[j]构成的字符串 $p_1$ 和p[i-j]和p[i]构成的字符串 $p_2$ 匹配。p[i] !== p[j]时，根据KMP算法的思想，i指向原始串aab中的b,j指向原始串aaf中的f，失配了，模式串P的指针j需要回退，而回退的位置就是next[j-1]，也就对应了代码中的

 while (j > 0 && p[i] !== p[j]) {
      j = next[j - 1]
    }

再解释一下为什么以next为参考进行回退。p[i] !== p[j]时，说明p[i]的加入是没法使得最长前缀长度继续加一了，那么只能有一种情况，缩短p[0]到p[i-1]字符串前后缀的长度，看看是不是再把p[i]就可以了。那么怎么缩短呢，去next数组里找。同时还要注意一点后缀的定义，后缀的结尾必然就是字符串的结尾。当我们按照next数组查找next[j]的时候，next中的j始终能够保证p[0]到p[j-1]构成的字符串同样出现在p[0]到p[i-1]构成的字符串的结尾。可以理解为还有一个指针k指向后缀的开始，当j向前到next[j-1]时，k也会向后移动j-next[j-1]个单位。可以分析aaaabaaaac为例。

那么再结合while的条件更具体地阐述一下。
为什么要有这个while，是因为for循环会使i++必须在当前这个for循环内部搞定这个next[i]才可以。
while另一个作用在于p[i] !== p[j]的条件判断，在j回退的过程中并不是一次回退(一次回退的话就是写的if)就可以完成的。
代码复制一遍便于查看

function getNext(p) {
  let next = [0], j = 0
  for (let i = 1; i < p.length; i++) {
    if(j > 0 && p[i] !== p[j]) {
      j = next[j - 1]
    }
    if (p[i] === p[j]) {
      j++
    }
    next[i] = j
  }
  return next
}

还是以aabcaaf为例，如果只回退一次j=1,而p[i] === p[j]不满足,next[i]=1，但是此时应该是没有匹配的前后缀。所以while和p[i] !== p[j]配合使用就能保证在跳出while时，满足p[i] === p[j]的条件，此时可以把i对应的字符加入到后缀中，j也可以++了。而j>0的目的就是防止一直往前找始终没有找到一个满足p[i] === p[j]的j。这也是为什么先判断p[i] !== p[j]的原因，因为很有可能此时j所对应的前缀中存在一个字串，使得i加入后缀以后仍然能够满足前后缀有匹配的部分。比如aabcaaa,在j回退到j=2时，跳出了while,p[i] === p[j],最长前缀长度能够加一,j能够++

KMP算法小记

一、第一种

1、初始化

2、p[i] === p[j]时

3、p[i] !== p[j]

推荐阅读更多精彩内容