当前位置：首页 > news >正文

4.7.KMP算法(新版)

news 2025/9/18 7:21:46

一.回顾：KMP算法基于朴素模式匹配算法优化而得来的

朴素模式匹配算法核心思想：把主串中所有长度与模式串长度相等的子串与模式串进行对比，直到找到第一个完全匹配的子串为止，如果当前尝试匹配的子串在某一个位置匹配失败，就立即进行下一个子串的匹配，而且是从下一个子串的头部开始一一匹配

例1：

模式串的最后一个字符与主串中第一个和模式串长度相等的子串匹配失败：

模式串与主串中第二个与模式串长度相等的子串比较，开始从2号字符开头的子串进行比较，之所以开始匹配2号字符开头的子串，且从2号字符开始比较，是因为在主串里的字符到底是什么无法得知，所以只能从主串里与模式串长度相等的子串的第一个字符依次往后匹配：

如果以2号字符开头的这个子串在某个字符上与模式串匹配失败，同理，由于主串里的字符未知，因此只能尝试匹配以3号字符开头的子串，并且要从3号字符开始依次往后与模式串进行对比，因为主串里包含的内容不得而知：

之后以此类推找主串中是否有要找的模式串。

换一种思路：

模式串的最后一个字符与主串中第一个和模式串长度相等的子串匹配失败，那么该子串中除了最后一个字符外都与模式串中除了最后一个字符外匹配成功，因此本例中模式串匹配到第6个字符才发现匹配失败，这种情况下就可以从模式串中得知主串中的前几个字符的内容，只有最后一个字符不知道，所以就要利用好此时主串中已知的字符：

根据朴素模式匹配算法的思想，如果当前的子串匹配失败，就要取下一个符合要求的子串与模式串进行对比，此时已经知道主串中前几个字符的信息，因此就会发现模式串的第一个字符就与此时要匹配的子串不匹配，所以当前的子串就没必要继续匹配下去，直接进行第三个符合要求的子串进行与模式串匹配：

现在的子串也是知道前几个字符的信息（本例中可以知道该子串前3个字符为aab），第一个字符可以和模式串第一个字符匹配，第二个字符就与模式串不匹配了，所以这个子串也没有必要继续匹配了：

同理，开始下一个子串的匹配，该子串的前两个字符是已知的，而且前两个字符匹配成功，但该子串里的第三个字符就不得而知了，所以对于现在的这个字符来说，前两个字符匹配成功，而第三个字符是否匹配成功暂时还不知道，因此一开始只需要从第三个字符开始往后检查匹配就可以了：

总结：

如本例中，模式串在与第一个子串进行匹配时，如果发现最后一个字符不匹配，那么就意味着前5个字符已得知，此时主串中以标记2为开头的子串和以标记3为开头的子串就无需匹配了，可以直接对比以标记4为开头的子串，而且在对比以标记4为开头的子串时，只需要从第三个字符开始检查即可，因为前两个元素已经确定和模式串匹配成功，这样就省去了大量的无效匹配：

KMP算法的思想：利用好模式串本身隐含的信息，要确定模式串的某一个元素发生匹配失败时接下来要如何处理，显然最终的结论并不依赖主串的内容，和匹配的主串的哪一个位置并没有关系，只和模式串的内容有关

例2：

主串中第一个符合要求的子串与模式串匹配时，在第5个字符上匹配失败：

此时主串中的前4个元素的具体信息是可以确定的，与模式串一致，从第5个元素开始后面的信息暂时不确定：

第一个子串匹配失败，开始下一个子串的匹配，显然匹配失败：

继续下一个子串的匹配，显然也不行：

继续下一个子串的匹配，已知的字符匹配成功，而未知的字符能否匹配成功暂时不得而知，所以本例中可以从该子串的第二个字符开始检查匹配：

例3：

主串中第一个符合要求的子串与模式串匹配时，在第4个字符上匹配失败：

此时主串中的前3个元素的具体信息是可以确定的，与模式串一致，从第4个元素开始后面的信息暂时不确定：

第一个子串匹配失败，开始下一个子串的匹配，显然匹配失败：

继续下一个子串的匹配，已知的字符匹配成功，而未知的字符能否匹配成功暂时不得而知，所以本例中可以从该子串的第二个字符开始检查匹配：

例4：

主串中第一个符合要求的子串与模式串匹配时，在第3个字符上匹配失败：

此时主串中的前2个元素的具体信息是可以确定的，与模式串一致，从第3个元素开始后面的信息暂时不确定：

第一个子串匹配失败，开始下一个子串的匹配，已知的元素当中匹配失败：

继续下一个子串的匹配，此时已知的元素全部用完：

例5：

主串中第一个符合要求的子串与模式串匹配时，在第2个字符上匹配失败：

此时主串中的第1个元素的具体信息是可以确定的，与模式串一致，从第2个元素开始后面的信息暂时不确定：

继续下一个子串的匹配，此时已知的元素全部用完：

例6：

主串中第一个符合要求的子串与模式串匹配时，在第1个字符上就匹配失败，此时就只能尝试匹配下一个符合要求的子串了：

前面的5个例子中都是主串指针不变，模式串指针变，本例中为了和前5个例子中的处理逻辑类似，可以先让模式串指针为0即指向模式串第一个元素的前一个位置，之后让主串指针和模式串指针都自增即可，这样就可以实现主串指针和模式串指针同时后移：

总结：

整合：

第一个子串与模式串在第6个字符上匹配失败，按照朴素模式匹配算法需要主串指针"回溯"，模式串指针变为1：

按照刚才的过程即利用主串指针不"回溯"，直接主串指针不变，修改模式串指针即可，省去了无效的对比：

进行此次的匹配，最终全部匹配成功，主串指针也无需"回溯"，大大提高了查找效率

通常来说主串要比模式串长很多，因此用主串指针不"回溯"的方法是非常高效的。

例7：

最终会因为模式串指针超出指定范围而停止。

二.利用代码实现主串指针不"回溯"的查找算法：

可以利用数组，该数组记录当某个元素匹配失败时模式串指针应该指向的值，注：当第一个元素就匹配失败时，就要把模式串指针设为0：

next数组记录当某个元素匹配失败时模式串指针应该指向的值
i为主串指针，j为模式串指针
S为主串，T为模式串
例如：j为6代表此时匹配到模式串里的第6个字符，如果此时第6个字符匹配失败，那么根据j=next[j]此时j更改为3

利用next数组进行匹配(主串指针不"回溯")的代码：形参中S为主串，T为模式串，next数组记录当某个元素匹配失败时模式串指针应该指向的值，函数体中i为主串指针，j为模式串指针，i和j都从1开始即从头部开始匹配，S.length表示主串的长度，T.length表示模式串的长度，S.ch[i]==T.ch[j]表示此时主串的元素等于模式串的元素

三.朴素模式匹配算法 v.s. KMP算法：

KMP算法相比于朴素模式匹配算法多了一个next数组以及对模式串指针为0时的判断，有了next数组就不需要主串指针"回溯"，只需要修改模式串的指针即可：

主串的长度为n，由于主串指针不"回溯"，所以模式匹配过程最坏时间复杂度就是O(n)即把整个主串都走了一遍，最终算整个算法的时间复杂度时只需要相加即可
KMP算法最坏时间复杂度为O(m+n)
KMP算法在效率上要优于朴素模式匹配算法

四.求next数组(next数组记录当某个元素匹配失败时模式串指针应该指向的值)：

注：next数组0索引上不存数据，从1索引开始

next数组的长度等于模式串长度加一，因为next数组存储数据的下标要和模式串的下标一一对应，此时模式串下标规定从1开始，而数组下标却从0开始，所以next数组的长度等于模式串长度加一，由上图也可知
比如next[1]代表模式串第一个字符，在next数组中next[1]的含义是当模式串的第一个字符发生匹配失败时模式串指针应该指向哪个位置
任何模式串都一样，第一个字符不匹配时，只能匹配主串里下一个符合要求的子串，因此，往后余生，next[1]都无脑写0
任何模式串都一样，第二个字符不匹配时，应尝试匹配模式串的第一个字符，因此，往后余生，next[2]都无脑写1

例一：

求next[1]，若模式串的第一个字符匹配失败，根据之前的分析，此时模式串指针的值赋值为0，然后模式串指针和主串指针同时自增即开始匹配往后的模式串和主串里的子串，所以next[1]为0：

求next[2]，若模式串的第二个字符匹配失败，意味着这时无法得知模式串的第二个字符所在的位置对应的主串里的该位置的字符，那么就只能让模式串往后滑动一位，也就是让模式串指针为1即next[2]为1：

求next[3]，若模式串的第三个字符匹配失败，此时可以由模式串得知主串里的两个字符(如下图)即分界线左边的两个字符，在分界线的左边的前两个字符，一个一个往后移动进行比对，如果比对成功就进行下一个字符的比对，如果失败直接后移模式串比对。例如本例中先移动一个字符，发现不匹配，然后继续往后移模式串，此时整个模式串就全部移动到分界线的右边了，而在分界线的右边，主串的内容就不得而知了，因此就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对，因此当模式串第三个字符匹配失败时，可以直接让模式串指针的值为1即next[3]为1：

求next[4]，若模式串的第四个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前三个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，根据题意，由于无法匹配成功最终模式串会全部移动到分界线右边，而且分界线右边的字符无法确定，所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对，所以当模式串第四个字符匹配失败时，可以让模式串指针的值为1即next[4]为1：

求next[5]，若模式串的第五个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前四个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，最终当分界线左边只剩下一个字符时开始匹配成功，由于分界线右边的字符未知，所以有必要开始模式串第二个字符的比对，因此当模式串第五个字符匹配失败时，可以让模式串指针的值为2即next[5]为2：

求next[6]，若模式串的第六个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前五个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，根据题意，由于无法匹配成功模式串最终会全部移动到分界线右边，而且分界线右边的字符无法确定，所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对，所以当模式串第六个字符匹配失败时，可以让模式串指针的值为1即next[6]为1：

到此，求出了字符串google的next数组。

应用例一中通过字符串google求出的next数组：

首先模式串的第六个字符匹配失败，根据求出来的next数组，模式串指针指向1：

此时模式串的第一个字符匹配失败，根据求出来的next数组，模式串指针指向0：

同时模式串指针和主串指针要自增，也就是开始匹配下一个子串：

此时模式串的第五个字符匹配失败，根据求出来的next数组，模式串指针指向2：

如下：

比对后最终匹配成功：

例二：

求next[3]，若模式串的第三个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前两个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，根据题意，由于无法匹配成功模式串最终会全部移动到分界线右边，而且分界线右边的字符无法确定，所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对，所以当模式串第三个字符匹配失败时，可以让模式串指针的值为1即next[3]为1：

求next[4]，若模式串的第四个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前三个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，当模式串移动到在分界线左边只剩下一个字符时开始匹配成功，由于分界线右边的字符无法确定，所以有必要开始模式串第二个字符的比对，因此当模式串第四个字符匹配失败时，可以让模式串指针的值为2即next[4]为2：

求next[5]，若模式串的第五个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前四个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，当模式串移动到在分界线左边剩下两个字符时开始匹配成功，由于分界线右边的字符无法确定，所以有必要开始模式串第三个字符的比对，因此当模式串第五个字符匹配失败时，可以让模式串指针的值为3即next[5]为3：

求next[6]，若模式串的第六个字符匹配失败，此时可以在匹配失败的字符左边画一条分界线，主串中这条分界线左边的前五个字符可以确定，而分界线右边的字符就无法确定，接下来需要模式串一步一步往右移动来比对，一边移动一边比对，当模式串移动到在分界线左边剩下三个字符时开始匹配成功，由于分界线右边的字符无法确定，所以有必要开始模式串第四个字符的比对，因此当模式串第六个字符匹配失败时，可以让模式串指针的值为4即next[6]为4：

到此，求出了模式串T的next数组。

五.求next数组的总结：

注：next数组0索引上不存数据，从1索引开始

六.next数组的优化思路：利用之前已求出next数组的模式串T即abaabc

例一：

若此时在第三个字符匹配失败：

根据next数组此时模式串指针应指向1即j为1：

由于第三个字符匹配失败，所以主串指针所指的字符和模式串指针所指的字符是不相等的，既然不相等，又此时模式串指针所指的是模式串的第三个字符a，说明主串指针所指的第三个字符一定不是a，因此当第三个字符匹配失败时，接下来需要让模式串指针指向1，但这一次的匹配一定会失败，因为模式串指针此时所指的字符是第一个字符a，这是已知的，而此时主串指针所指的元素虽然未知，但它一定不是a，第一个字符匹配失败时需要模式串指针指向0，然后模式串指针和主串指针自增：

所以，一开始发现模式串第三个字符和主串第三个字符匹配失败时，又因为模式串里的第一个字符和第三个字符相等，所以模式串里的第一个字符和主串里的第三个字符也一定会匹配失败，因此，一开始发现模式串第三个字符和主串第三个字符匹配失败时就可以直接让模式串指针指向0，因为如果让模式串指针指向1时意味着接下来是让模式串第一个字符和主串第三个字符开始匹配，根据之前的分析，该匹配注定失败，当第一个字符匹配失败时，应该让模式串指针指向0，所以最好的处理方式就是直接让模式串指针指向0（这样就可以跳过多余的模式串第一个字符匹配主串第三个字符）：

最终优化后，当第三个字符匹配失败时，直接让模式串指针指向0，然后模式串指针和主串指针自增，意味着跳过了多余的模式串第一个字符匹配主串第三个字符：

例二：

若此时在第五个字符匹配失败：

根据next数组此时模式串指针应指向2即j为2：

由于第五个字符匹配失败，所以主串指针所指的字符和模式串指针所指的字符是不相等的，既然不相等，又此时模式串指针所指的是模式串的第五个字符b，说明主串指针所指的第五个字符一定不是b，因此当第五个字符匹配失败时，接下来需要让模式串指针指向2，但这一次的匹配一定会失败，因为模式串指针此时所指的字符是第二个字符b，这是已知的，而此时主串指针所指的元素虽然未知，但它一定不是b，第二个字符匹配失败时需要模式串指针指向1：

最终优化后，当第五个字符匹配失败时，直接让模式串指针指向1，意味着跳过了多余的模式串第二个字符匹配主串第五个字符：

最终优化后演示：

例三：

若此时在第六个字符匹配失败，可以确定主串第六个字符一定不是c：

根据next数组此时模式串指针应指向3即j为3，模式串第三个字符为a，主串里的第六个字符一定不是c，但是否是a就无法确定了，所以此时就有必要进行匹配判断，因此当六个字符匹配失败时，让模式串指针指向3是有必要的，无需继续优化：

结论：当匹配失败时，判断模式串指针要指向的下一个模式串字符和原本失配的字符是否相等，如果这两个字符不相等，next数组的值保持不变，如果这两个字符相等，此时可以更改next数组的值实现优化

KMP算法的进一步优化本质是优化next数组
nextval数组其实就是next数组的优化，也可以把nextval数组理解为新的next数组，nextval数组可以命名为next数组

七.求nextval数组：nextval数组其实就是next数组的优化，也可以把nextval数组理解为新的next数组，nextval数组可以命名为next数组

注：nextval数组0索引上不存数据，从1索引开始，nextval数组1索引上的数据固定为0即nextval[1]=0（原理和next数组1索引上的数据固定为0的原理一样）从2索引开始就需要一步一步推导

练习1：

函数解读：

j为模式串指针，T.length为模式串的长度，T.ch[j]为模式串T在j索引上的字符
一般都是先求出next数组，再求nextval数组
j代表模式串指针当前所指的字符，next[j]代表模式串指针应更改为所指向的字符
next数组和nextval数组所包含的内容都是一样的即把当前模式串指针的值修改为下一次要指向的值
该函数中nextval数组存储的值都是从next数组得出的，也就是说nextval的元素是next[j]
如果当前j所指的字符和next[j]所指的字符不相等，那么就让nextval[j]=next[j]，意味着nextval数组在j索引上的值等于next数组在j索引上的值。例如上述图片中求nextval[2]，此时代表模式串第二个字符匹配失败且j等于2，其中j指向第二个字符即b，next[j]（即next[2]）等于1即模式串指针应该改为指向模式串第一个字符即a，由于字符a和b不相等，所以nextval[2]等于next[2]即nextval[2]=1
如果当前j所指的字符和next[j]所指的字符相等，那么就让nextval[j]=nextval[ next[j] ]，nextval[ next[j] ]可以理解为next数组的嵌套，当j指针即模式串指针指向的字符匹配失败时需要指向next[j]所指的字符，根据题意，next[j]所指的字符注定会匹配失败，此时就需要把模式串指针改为next[ next[j] ]即nextval[ next[j] ]。例如上述图片中求nextval[3]，此时代表模式串第三个字符匹配失败且j等于3，其中j指向第三个字符即a，next[j]（即next[3]）等于1即模式串指针应该改为指向模式串第一个字符即a，由于字符a和a相等，所以nextval[3]等于nextval[ next[3] ]即nextval[3]=0，其实不难理解，因为此时模式串第一个字符a和模式串第三个字符a相等，所以当模式串第三个字符匹配失败时，那么模式串第一个字符注定会匹配失败，所以没必要再对比模式串的第一个字符，而是直接考虑模式串第一个字符匹配失败后应该跳到哪个字符进行匹配