41 串的KMP模式匹配算法观察：理解困难
你好，我是王健伟。
上节课我带你学习了串的朴素模式匹配算法，这种算法思想简单，执行效率不高。为什么这么说呢？我带你仔细分析一下。
朴素模式匹配算法的问题
串的朴素模式匹配算法经常可以看到主串的指针point1回退的情形。导致匹配时间增加。看一下图1：
图1中，在主串中寻找子串“google”内容，开头的“googl”都相同，但比较到第6个字符时，主串内容为‘o’，子串内容为‘e’，此时情形如图2所示：
那么point1指针就要从下标为5的位置回退到下标为1的位置，为什么回退到下标为1的位置呢？其实很容易看得出来，只需要把子串位置向右移动一个位置，而后子串的开头字符对应的是哪个下标，主串的指针point1就回退到哪个下标位置，下一次比较就是主串中下标1位置的字符o与子串的开头位置的字符g作比较。如图3所示：
其实，整个串的朴素模式匹配算法的执行过程也可以看作是子串不断右移与主串对应位置字符逐个比较的过程。这个过程中，point1指针在字符比较失败的情况下往往需要回退（左移）若干位置来重新与子串的各个字符比较，整个算法的执行效率显然不会很高。
正是因为串的朴素模式匹配算法是比较低效的，所以又提出了KMP算法。KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt三位大神提出的，因此人们称它为克努特—莫里斯—普拉特算法（简称KMP算法）。
KMP模式匹配算法观察1
KMP算法的核心是利用匹配失败后的信息，尽量减少子串（模式串）与主串的匹配次数以达到快速匹配的目的。换句话说，KMP算法会让主串中的指针（point1）不回退，而且甚至看起来子串一次可能会右移多个位置。所以KMP算法的执行效率一般会更高。
光说理论你可能不太好理解，我们以图4来说明KMP算法：
在图4中，主串和子串字符依次对比。可以看到，前面5个字符主串和子串完全匹配，而下标5位置主串的字符为b，子串字符为a，主串和子串在这个位置不匹配了。
此时在子串中，观察这个不匹配字符左侧部分字符“abbab”，可以看到左右两端有两个子部分ab是完全匹配的，这个ab就称为子串的前缀和后缀（公共前后缀）：
如图5所示：
这里引入了两个概念，前缀和后缀。
一个字符串的前缀是包含首字符不包含尾字符的所有子串。比如字符串abbab的前缀可以是a、ab、abb、abba，但abbab就不是前缀。
而一个字符串的后缀是包含尾字符不包含首字符的所有子串。比如字符串abbab的后缀可以是b、ab、bab、bbab，但abbab就不是后缀。
目前，我们观察图4，有两点需要说明：
- 下标5位置前的主串和子串中字符相同——都是abbab。
- 子串中下标5位置前的部分有公共前后缀——ab。
此时，把公共前缀移动到公共后缀的位置。注意看，子串依次向后移动了多个位置，效率肯定更高。那在写程序的时候怎么体现子串向后移动了多个位置呢？其实只是设置一下point2指针的位置不再从字串的0下标开始而是从子串的2下标开始。
这就是KMP算法的核心移动方法，如图6所示：
观察图6中子串位置，可以发现，这样移动后的子串中前缀“ab”与主串中的“ab”是匹配的。因为一方面，公共前后缀是匹配的，另一方面，子串移动之前point2指针左边的内容与主串是匹配的。
OK，现在我们引入一个概念，最长公共（相等）前后缀。什么意思呢？如果模式串中有多对公共前后缀，那么其中最长的那一对就是最长公共前后缀。
接着图6，我们继续向后匹配，下标9位置对应的字符又不匹配了。如图7所示：
在子串中，观察这个不匹配字符左侧部分字符“abbaba”，找到最长的公共前后缀，可以看到左右两端只有字符a是完全匹配的，所以字符a作为最长公共前后缀，如图8所示：
所以，下一步就把公共前缀移动到公共后缀的位置，如图9所示：
当然，比较还没有完成，其余的比较步骤怎么做，作为作业留给你完成。但是，在做这个作业之前，先看看下面的内容，只要看得明白，那么这个作业做起来将非常容易。
KMP模式匹配算法观察2
为了加强对KMP模式匹配算法的理解，看看下面这个范例，该范例只要能看懂，KMP模式匹配算法实现代码就能够写出来。下面图中的主串内容不用关心，只需要关注子串内容即可。
这里我们分为两种情况来讨论，下标0位置与主串不匹配，以及0位置字符匹配的各类情况。
- 下标0位置与主串不匹配
如果下标0位置与主串不匹配，则子串右移一个位置。右移是一个形象的比喻词，这里让指向主串的指针point1右移一个位置，就达到了子串右移一个位置的效果。这样后续可以用子串的第1个字符与主串的第2个字符（下标为1的字符）做比较，如图10所示：
图10可以看到，下标0号位置子串的字符（子串第1个字符a）如果与主串字符不匹配则后续就要用子串的第1个字符（字符a）与主串下一位（1号下标位）字符做比较。
- 0位置字符匹配
在这种情况下，我们一个一个来说。如果下标1位置与主串不匹配，则找下标1位置左侧的公共前后缀，但下标1位置左侧只有1个字符a，所以不存在公共前后缀。所以子串的第1个字符直接与主串当前位置的字符做比较，相当于子串右移了1个位置。如图11所示：
图11可以看到，下标1号位置子串的字符如果与主串字符不匹配则后续就要用子串的第1个字符（字符a）与主串当前位（1号下标位）字符做比较。
如果下标2位置与主串不匹配，则找下标2位置左侧的公共前后缀，但左侧内容是“ab”，所以不存在公共前后缀。所以子串的第1个字符直接与主串当前位置的字符做比较，相当于子串右移。如图12所示：
图12可以看到，下标2号位置子串的字符如果与主串字符不匹配则后续就要用子串的第1个字符（字符a）与主串当前位（2号下标位）字符做比较。
如果下标3位置与主串不匹配，则找下标3位置左侧的公共前后缀，因为左侧内容是aba，最长公共前后缀是a，所以子串的前缀移动到后缀的位置（即point2 = 1）再与主串对应位置的字符做比较，如图13所示：
图13可以看到，下标3号位置子串的字符如果与主串字符不匹配则后续就要用子串的第2个字符（字符b）与主串当前位（3号下标位）字符做比较。
如果下标4位置与主串不匹配，则找下标4位置左侧的公共前后缀，因为左侧内容是abab，最长公共前后缀是ab，所以子串的前缀移到后缀的位置（即point2 = 2）再与主串对应位置的字符做比较，如图14所示：
图14可以看到，下标4号位置子串的字符如果与主串字符不匹配则后续就要用子串的第3个字符（字符a）与主串当前位（4号下标位）字符做比较。
如果下标5位置与主串不匹配，则找下标5位置左侧的公共前后缀，因为左侧内容是ababa，注意最长公共前后缀是什么？是aba，所以子串的前缀移到后缀的位置（即point2 = 3）再与主串对应位置的字符做比较，如图15所示：
图15可以看到，下标5号位置子串的字符如果与主串字符不匹配则后续就要用子串的第4个字符（字符b）与主串当前位（5号下标位）字符做比较。
你不难发现一个规律——如果公共前后缀长度为n，那么就需要用子串的第n+1个字符与主串当前位做比较。
如果下标6位置与主串不匹配，则找下标6位置左侧的公共前后缀，因为左侧内容是ababaa，最长公共前后缀是a，所以子串的前缀移到后缀的位置（即point2 = 1）再与主串对应位置的字符做比较，如图16所示：
图16可以看到，下标6号位置子串的字符如果与主串字符不匹配则后续就要用子串的第2个字符（字符b）与主串当前位（6号下标位）字符做比较。
如果下标7位置与主串不匹配，则找下标7位置左侧的公共前后缀，因为左侧内容是ababaaa，最长公共前后缀是a，所以子串的前缀移到后缀的位置（即point2 = 1）再与主串对应位置的字符做比较，如图17所示：
图17可以看到，下标7号位置子串的字符如果与主串字符不匹配则后续就要用子串的第2个字符（字符b）与主串当前位（7号下标位）字符做比较。
其他下标位置与主串不匹配的详细信息，它们的分析方法和上述相同，这里我也想细说一下。
- 下标8号位置子串的字符如果与主串字符不匹配则后续就要用子串的第3个字符（字符a）与主串当前位（8号下标位）字符做比较。
- 下标9号位置子串的字符如果与主串字符不匹配则后续就要用子串的第4个字符（字符b）与主串当前位（9号下标位）字符做比较。
- 下标10号位置子串的字符如果与主串字符不匹配则后续就要用子串的第5个字符（字符a）与主串当前位（10号下标位）字符做比较。
- 下标11号位置子串的字符如果与主串字符不匹配则后续就要用子串的第6个字符（字符a）与主串当前位（11号下标位）字符做比较。
整理上边罗列的信息可以总结成：主串与子串哪个下标位置不匹配时**，子串就**从哪个字符开始继续与主串字符做比较。如下图18所示：
图18中，竖形显示的文字中，第一列文字与其他列文字（除数字外）是不同的。所以第一列文字用数字0表示。其他列文字分别用该列所包含的数字代替，所以其他列数字应该为1、1、2、3、4、2、2、3、4、5、6。把这些信息放入到一个数组中。如图19所示：
这个数组中蕴含的信息非常重要，因为通过这个数组中的信息，任何一个子串位置上发生与主串字符不匹配时都会知道下一步该如何做，也就是知道下一步用子串的哪个字符与主串的哪个字符进行比较。所以这个数组也叫“下一步”数组，也就是next数组，这个数组也称为前缀表（前缀数组）。
而且不难看到，对于任何一个next数组：
- 下标为0的元素肯定是0，而且其他下标的元素肯定都不为0。
- 下标为1的元素肯定是1。因为该位置左侧只有1个字符，所以不存在公共前后缀。
需要注意的是不同的代码实现方式next数组中的内容可能不同，但next数组存在的目的和表达的含义却都相同。现在，换一种说法来表达next数组存在的意义：指示当子串中某个位置的字符与主串相应位置字符不匹配时，应该将子串中的哪一位字符与主串中的当前位/下一位字符做比较。
小结
这节课，我们详细分析了查找子串时采用朴素模式匹配算法效率不高的原因：主串指针经常回退导致匹配时间增加。因为串的朴素模式匹配算法是比较低效的，所以提出了KMP算法这种改进的字符串匹配算法。
KMP算法的核心是利用匹配失败后的信息，尽量减少子串与主串的匹配次数，从而达到快速匹配的目的。KMP算法通过让主串中的指针不回退，甚至看起来子串一次可能会右移多个位置来提高查找子串时的执行效率。
接着，我也带你通过观察的方式详细解释了KMP算法的实现原理、步骤、核心移动方法，在这个过程中，我引入了几个概念，分别是“前缀”“后缀”“最长公共前后缀”。
KMP算法的代码实现特点是代码实现简短，但支持这些简短代码的实现理论却很晦涩、难以理解。所以，我又进一步站在代码编写的角度，带着你描述了各个位置子串与主串不匹配时子串的移动方法，希望能够帮助你理解KMP算法的实现步骤。
总结下来，就是将这些子串的移动信息汇集到一个被称为next的数组中，该数组用来指示当子串中某个位置的字符与主串相应位置字符不匹配时，应该将子串中的某一位字符与主串中的当前位/下一位字符做比较。有了next数组，就为下一步编写代码实现KMP算法做好了准备了。
思考题
上面图9所示的KMP算法比较还没有完成，其余的比较步骤怎么做，请你尝试通过画图来完成。
欢迎你在留言区和我交流。如果觉得有所收获，也可以把课程分享给更多的朋友一起学习。我们下节课见！
- TableBear 👍（1） 💬（1）
老师会讲next数组的构造吗？
2023-05-17 - Yj.yolo 👍（1） 💬（0）
图16下图应该是错了吧，point2应该指向位置2，但是图中指向位置3了
2023-06-28