正文

经典算法——kmp，深入讲解next数组的求解(代码片段)

雷八天  雷八天  2022-12-13  518

关键词：

前言　　

　　之前对kmp算法虽然了解它的原理，即求出P₀···P_i的最大相同前后缀长度k；但是问题在于如何求出这个最大前后缀长度呢？我觉得网上很多帖子都说的不是很清楚，总感觉没有把那层纸戳破，后来翻看算法导论，32章字符串匹配虽然讲到了对前后缀计算的正确性，但是大量的推理证明不大好理解，没有与程序结合起来讲。今天我在这里讲一讲我的一些理解，希望大家多多指教，如果有不清楚的或错误的请给我留言。　

1.kmp算法的原理：

　　本部分内容转自：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

字符串匹配是计算机的基本任务之一。

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？

许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11.

因为空格与A不匹配，继续后移一位。

12.

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

13.

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

15.

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；

　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

16.

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

2.next数组的求解思路

　　通过上文完全可以对kmp算法的原理有个清晰的了解，那么下一步就是编程实现了，其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。我先给出我的代码：

void makeNext(const char P[],int next[])

    int q,k;//q:模版字符串下标；k:最大前后缀长度
    int m = strlen(P);//模版字符串长度
    next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
    for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
    
        while(k > 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k
            k = next[k-1];          //不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解  
        if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
        
            k++;
        
        next[q] = k;

　　现在我着重讲解一下while循环所做的工作：

　　已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；
　　此时比较第k项P[k]与P[q],如图1所示
　　如果P[K]等于P[q]，那么很简单跳出while循环;
　　关键！关键有木有！关键如果不等呢？？？那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀，可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢？？？是啊！为什么呢？原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](j==next[k-1])，看看它的下一项P[j]是否能和P[q]匹配。如图2所示

附代码：

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])

    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k])
        
            k++;
        
        next[q] = k;
    


int kmp(const char T[],const char P[],int next[])

    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        
            q++;
        
        if (q == m)
        
            printf("Pattern occurs with shift:%d\\n",(i-m+1));
        
        


int main()

    int i;
    int next[20]=0;
    char T[] = "ababxbababcadfdsss";
    char P[] = "abcdabd";
    printf("%s\\n",T);
    printf("%s\\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i)
    
        printf("%d ",next[i]);
    
    printf("\\n");

    return 0;

kmp算法模式匹配——手工求解next和nextval数组值

本文需要了解KMP算法基本流程和相关概念，如有问题，请先进行基础学习：链接:天勤-KMP算法易懂版求解next数组值给定模式串：“ababaaab”，求解其next数组值。例子里面的ababaaab，我们定义一个i为模式串的... 查看详情

kmp算法求next数组

next数组的求解方法是：第一位的next值为0，第二位的next值为1。后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向... 查看详情

kmp算法(代码片段)

目录简述暴力算法与整体框架暴力KMP框架next数组最长前缀后缀引理根据引理求解next数组f数组求解求解模板题总结简述KMP算法，又称模式匹配算法，能够在线性时间内判定字符串(A[1-N])是否为字符串(B[1-M])的子串。对于刚刚接触KM... 查看详情

kmp算法讲解(代码片段)

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹... 查看详情

kmp算法中next数组手工求解

参考技术AKMP算法是一种改进的字符串匹配算法，如果不研究编码的话，手工实现还是比较简单，小型字符串甚至不需要你去求next数组就能看出来怎么移动。但是会有一些题目让你求解next数组，这里就以一个题目讲一下手工求解... 查看详情

kmp算法的next函数求解和分析过程

...//blog.csdn.net/wang0606120221/article/details/7402688 假设KMP算法中的模式串为P，主串为S，那么该算法中的核心是计算出模式串的P的next函数。KMP算法是在已知的模式串的next函数值的基础上进行匹配的。由于本次只讨论next的求值过... 查看详情

顺序串的bf算法kmp(找next数组的值)算法

bf算法难度一般，kmp算法难度一般但是其中的找next[j]的算法比较难，很多小伙伴不好听明白，在这我推荐你们看这个链接的视频（https://www.bilibili.com/video/av714697013/）讲解的很明白通过动画理解代码的意义，这个不好理解多看多... 查看详情

kmp算法模式匹配——手工求解next和nextval数组值

kmp算法

废话不多说，看毛片算法的核心在于next数组。很多地方用的都是严书上的方法来求解next数组，代码确实简洁明了，但是可能对于初学者来说不容易想到，甚至不是一下子能理解。(好了，其实我说的就是自己，别笑)以下为严师... 查看详情

从头到尾彻底理解kmp

...不够，故才迟迟没有修改本文。然近期因开了个算法班，班上专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发... 查看详情

[数据结构]kmp算法(代码片段)

目录1、暴力匹配（BF）算法2、KMP算法next数组（手动求，方便求解题目）值得思考的两点注意：日常数据结构题目问next数组的值，需要在此方法求出next基础上，全部加1next数组（公式求，方... 查看详情

kmp算法详解——多图，多例子（c语言）(代码片段)

目录前言1.KMP算法是什么？2.为什么需要KMP算法？2.1主串找字串2.2暴力求解3.KMP准备工作3.1字符串的前后子串3.2最大前后相等子串3.3最大前后相等子串练习4.KMP算法4.1简看KMP算法5Next数组 5.1j该回溯的位置 5.2学会计算... 查看详情

kmp算法

JUly的文章：从头到尾彻底理解KMP KMP算法：复杂度：线性PMT数组：PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。next数组：是将PMT数组向后偏移一位得到的数组。基于next数组进行匹配。 next数组的求... 查看详情

如何求字符串next数组值

...同理计算4a，可得计算结果为2+1=3。扩展资料next的优点KMP算法优于简单字符串匹配算法的根本原因就是：引入了一个next数组，这个数组可以尽可能的记录相关的匹配信息，使得在不匹配发生的时候移动的步长不再是固定的一位，... 查看详情

关于kmp算法中，获取next数组算法的理解

参考：KMP入门级别算法详解--终于解决了（next数组详解）https://blog.csdn.net/lee18254290736/article/details/77278769在这里讨论的next数组的含义为模式串p[j]之前前缀和后缀相等的个数，若都不相等则为0。（特殊情况，没有前缀和后缀时,则... 查看详情

kmp求解next与nextval(代码片段)

一.示例图二.经典例题例题图片来自王道数据结构书中仅为个人复习方便所写，如有侵权立即删除！查看详情

kmp算法的next[]数组通俗解释

...中查找一个子字符串有很多方法。KMP是一种最常见的改进算法，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。当然我们可以看到这个算法针对的是子串有对称属性，如果有对称属性，那么就需... 查看详情

bzoj3670[noi2014]动物园kmp-next数组

...让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解KMP算法。园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习... 查看详情