算法修炼笔记一、KMP算法

一、引入

本篇文章主要是对KMP算法进行分析, 首先KMP算法解决的一个问题是: 判断一个字符串match是否是另一个字符
串str的子串

只是说对这个问题的解决中, 有一个非常著名的算法叫KMP, 以O(N)级别的时间复杂度完成了该问题的解决, 在
说KMP算法之前, 我们以暴力解的方式来描述下该问题的解决, 要想判断match是否是str的子串, 那么就需要从
str索引位置为0的位置开始与match进行匹配, 如果索引为0的字符两者都相等, 那么判断的位置就开始往下一个
索引移动, 即索引位置为1, 如果一直匹配到索引位置为X时发现两个字符不相等, 那么本次匹配失败, match对
应的匹配位置就要重新回到0, 而str则从1开始, 即变成了从str[1, str.length-1]这个子串中和match[0]
进行匹配, 判断match是否是str的子串

这就是暴力解, 暴力解的根本目的就是将match从str的每一个子串进行匹配, 想象一下如下的匹配场景:

• str: abczkkabczkkabcs
• match: abczkkabcs

假设我们对str进行匹配match, 可以看到, 两者都存在abckkkabc, 当str和match的索引均为8的时候, 匹配
都是相等的, 直到下一个字符的匹配, 即str为z, 而match为s, 那么此时两个字符由于不相等, 导致str匹配的
位置要退回到索引位置为1即字符b, 而match则退回到0, 重新开始匹配是否在bczkkabczkkabcs中存在子串
match, 其实我们可以看到, 完全可以直接丢弃str的前面的abczkk这几个字符, 即从str中index位置为6开始
对match进行匹配, 从而实现一种快进的效果, 这就是KMP算法完成的功能

二、next数组的引入

在说KMP算法的时候, 就不得不提到KMP算法的一个核心next数组, 首先next数组是一个int[], 我们先不说
next数组的真正语义, 而先引入next数组的数据是怎么样的, 我们以字符串abcabcx为例子:

1. next数组: {0, 0, 0, 0, 1, 2, 3}
2. 先说next数组中这个值3, 原因是abcabcx中, x之前的字符串为abcabc, 而前缀和后缀中最长的相等字符串abc, 长度为3
3. 再来说这个值2, 原因是abcabc中, 最后一个字符c之前的字符串abcab, 前缀和后缀中最长的相等字符串ab, 长度为2
4. 再来说这个值1, 原因是abcab中, 最后一个字符b之前的字符串abca, 前缀和后缀最长的相等字符串为a, 长度为1

经过上面的例子分析, 我们再来看看next数组的描述: next数组每个索引x保存的是字符串从0到索引x – 1构成
的子串中前缀和后缀最长的相等子串长度, 其中前缀不能包括最后一个字符, 后缀不能包括第一个字符, 比如
aaac, 索引位置为3的时候, 前缀和后缀最长的相等子串为aa, 而不是aaa, 因为前缀不能包括最后一个a, 后缀
不能包括第一个a, 我们先不用理会这个next数组是怎么生成的, 再回过头来看KMP算法的实现, 假设我们已经对
match字符串生成了对应的next数组, 这个数组则表示的是match字符串每个索引位置前的子串中, 相等的前缀
和后缀的最大长度, 有了这个数据作为基础, KMP算法实现匹配位置的快进功能就有了保障

三、KMP算法

1、整体流程

首先, 我们的问题是: 判断字符串match是否另外一个字符串str的子串, 其次我们有一个已知的数据, 就是上
面说的next数组, next数组每个索引位置X保存的是match字符串从0到X – 1这个子串中, 相同的前缀和后缀的
最大长度, 其中前缀不包括索引位置为x-1这个字符, 后缀不包括索引位置为0这个字符

然后, 我们以str为abcabeabcabf, match为abcabf为例子(如下图), 根据match字符串生成的next数组为
{0, 0, 0, 0, 1, 2}

1. 经过一系列的比较, str的匹配索引即strIndex来到了5这个位置, match同时来到了5这个位置即matchIndex, 前面几个字符都是相等的, 比较str[strIndex]和match[matchIndex]的两个字符, 发现不相等

2. 此时str的strIndex索引位置不会发生改变, 并且在整个的查找过程中, strIndex只会增大直到str.length, 而不会出现减小的情况(在这种情况下, 相比于暴力解来说, 暴力解在第一次出现字符不同的情况下会将strIndex回滚到1这个位置, 下一次则是回滚到索引为2这个位置, 但是很明显第一次回滚时1这个位置的字符b跟match中第一个字符是不相等的, 即回滚过度了, 这就是暴力解的弊端, 回滚过度)

3. 而发生变化的是matchIndex, 根据next[matchIndex]得出, 相等的前缀和后缀最大长度为2, 即前缀和后缀均为ab, 那么此时会将matchIndex后退成位置1, 即matchIndex变为了2

4. 经过这一次的后退, 我们发现, 其实是对str从[3, str.length – 1]这段的子串中去查找match字符串, 并且此时已经比较完了str[3, 4]和match[0, 1]这两个位置的字符了, 而此时继续比较strIndex和matchIndex两个位置的字符, 由此可以发现, 我们str比较的位置进行了快进, 在暴力解中, 在上述情况下出现了不一致的时候, 变成了从str[1, str.length – 1]这段子串中去查找match字符串, 并且matchIndex会变为0, 而strIndex会变成1, strIndex和matchIndex均属于回退过度的情况

2、推断快进的原理

在进行下一步的流程分析之前, 我们以目前的状态进行分析快进的原理

• 问题一: 为什么matchIndex退回到位置一, 就等于变成了str从位置3开始到末尾构成的这个子串中查找match
  字符串

• 解答: 根据上面这张图中的颜色分类, 我们分为了红色区域, 蓝色区域, 绿色区域, 首先在matchIndex回退之前, 我们是对e和f这两个字符进行比较, 发现不相等, 于是开始对matchIndex进行回退, 首先我们了解到, 从match[0, matchIndex – 1]和str[0, strIndex-1]这两段字符串是相等的,由于:

  • 绿色区域(前缀) == 蓝色区域(后缀)
  • 蓝色区域(后缀) == 红色区域(后缀)

  得出, 绿色区域 == 红色区域, 进而得出我们接下来应该将strIndex与绿色区域的后一个位置的字符进
  行比较, 从而就变成了从str红色区域开始的子串中查找match字符串的流程, 这就是快进的原理

• 问题二: 为什么我们的目标从str[0, str.length – 1]这个字符串中查找match变成了str[位置3, str.length – 1]这个字符串中查找match, 在0与位置3之间的任意一个位置X, 不能从str[X, str.length – 1]查找match吗?(注意, 此时matchIndex没有发生回退, 还是在图中的位置)

• 解答: 假设我们能从str[X, str.length – 1]中查找match这个字符串, 那么意味着, str[X, strIndex-1]这段字符串跟match字符串的从[0,matchIndex-1]是一模一样的, 也就是说在这种假设存在的情况下match数组的[0, X]这个位置前缀和str[0, matchIndex-1]这个字符串中的一个子串[X, matchIndex-1]是相等的, 那么就意味着必然存在match字符串此时的相等前缀和后缀的最大长度是大于2的, 而根据next数组目前的定义, 相等的前缀和后缀最大长度为2, 与实际情况不相同, 所以假设失败

经过上面两个推论, 我们明白了, 当出现了匹配字符不相等的情况下, matchIndex应该变成
next[matchIndex]对应的值进行再一次的匹配, 如果此时matchIndex的字符和strIndex相等, 那么两者加1,
对str和match中下一个字符进行匹配, 如果两者不相等, 那么matchIndex需要再一次的进行回退

3、继续整体流程的分析

如下图所示:

1. 经过matchIndex的回退后, matchIndex此时处于位置1, 即matchIndex = 2, strIndex仍然为5
2. 判断发现match[matchIndex]和str[strIndex]不相等, 于是matchIndex又要再一次回退,
   next[matchIndex]为0, 索引matchIndex变为0, 即matchIndex回退到了位置2
3. 此时变成了对match[0]和str[5]进行比较, 两者不相等, strIndex + 1, 即此时变成了从
   str[strIndex, str.length-1]这个子串中查找match字符串
4. 由于后面的字符都相等, 所以strIndex和matchIndex都会多次同时加1, 最后, strIndex变为
   str.length, matchIndex变为match.length, 匹配结束, 匹配成功

四、next数组的生成

由字符串match生成next数组, next数组表示的语义是: next数组每个索引x保存的是字符串从0到索引x – 1构
成的子串中前缀和后缀最长的相等子串长度, 其中前缀不能包括最后一个字符, 后缀不能包括第一个字符

我们以下图来看看next数组的生成流程:

1. 我们期望对字符串abcabf?生成next数组, 假设我们此时已经将0-5索引位置的数据生成完毕了, 我们期望对索引为targetIndex的这个字符生成next数组中对应的数据, 首先我们不用考虑索引位置为targetIndex的这个字符是什么, 因为我们要获取的是从match[0, targetIndex – 1]这个子串中最长的前缀和后缀的匹配长度, targetIndex为6, targetIndex – 1即为5
2. 首先我们知道next[5]为2, 即表示相等的前缀和后缀的最大长度为2, 即表示match[0,1]构成的字符与match[3,4]构成的字符ab确实是相等的, 那么next[6]的值则需要判断match[3]和match[5]这两个字符的情况
3. 如果match[3] == match[5], 那么next[6] = next[5] + 1, 相信这一步大家应该很好理解
4. 由于match[3] != match[5], 所以就需要对匹配的位置进行回退, 那么就需要获取索引位置为3时的相等的前缀和后缀的最大长度, 即next[3]的值, 进而判断match[next[3]]和match[5]的关系, next[3]为0
5. 由于match[0] != match[5], 匹配的值应该进一步回退, 但是因为已经回滚到0了, 所以没法继续回退了, 从而得出next[6]为0, 即索引位置为6的情况下, match[0,5]构成的子串中最长的前缀和后缀的匹配长度为0

next数组的生成其实有点类似于KMP算法中match字符串中matchIndex的回退过程, 如果对KMP算法上述流程理解
清楚了, next数组的生成理解起来就会非常轻松了, 同样的, 如果需要推断为啥在next数组中这样回退, 可以
参考4.2中快进的原理分析, 和这个是类似的, 特别是问题2的推论

五、总结

KMP算法: 在一个字符串中查找一个子串是否存在, 核心是next函数得到的next数组, 以及回退原理的推导过
程, 后者是我们理解KMP算法的核心, 通过KMP算法, 使得我们解决这个问题的时间复杂度由O(N*M)变
成了O(N)级别, KMP算法的解决方案可以衍生出很多类似的问题, 这些问题都是通过将原问题变成问
题[在一个字符串中查找一个子串是否存在]来进行解决的, 比如判断一个字符串str是否是另一个字符
串str2的回环字符串

本文主要目的是以图文的形式分析KMP算法的流程, 并且进行原理分析, 没有提供出KMP算法的代码, 大家有兴趣
可以自己实现这样的代码, 然后对比网上的代码看看