严蔚敏-数据结构-kmp算法详解

kmp算法原理KMP算法（Knuth-Morris-Pratt算法）是一种用于快速搜索字符串中某个模式字符串出现位置的算法，由Knuth, Morris 和 Pratt于1977年提出。

KMP算法的工作方式如下：首先，给定一个主串S和一个模式串P，KMP算法的第一步就是先构造一个新的模式串P，其中的每一项存储着P中每一个字符前面由不同字符串组成的最长前缀和最长后缀相同的子串。

接着，在S中寻找P，它会从S的第一个字符开始，如果匹配上，就继续比较下一个字符，如果不匹配上，就根据P中相应位置上保存的信息跳到特定位置，接着再开始比较，如此不断循环下去，直到从S中找到P为止。

KMP算法的思路特别巧妙，比较效率很高，它的复杂度为O（m+n），其中m为主串的长度，n为模式串的长度。

它取代了以前的暴力搜索算法，极大地提高了程序的性能。

KMP算法的实现过程如下：（1）首先确定模式串P的每一个字符，构造模式串P的next数组：next[i]存储P中第i个字符之前最长相同前缀和后缀的长度（P中第i个字符之前最长相同前缀和后缀不包括第i个字符）；（2）接着从S中的第一个字符开始比较P中的每一个字符，如果字符不匹配，则采用next数组中保存的信息跳到特定位置，而不是暴力比较，以此不断循环，直到从S中找到P为止。

KMP算法是由Don Knuth, Vaughan Pratt和James Morris在1977年提出的。

它的思想是利用之前遍历过的P的信息，跳过暴力比较，可以把字符串搜索时间从O（m×n）降低到O（m+n）。

KMP算法在很多领域有着重要的应用，如文本编辑，模式匹配，编译器设计与多项式字符串匹配等等，都是不可或缺的。

数据结构（三）串---KMP模式匹配算法之获取next数组⽬录（⼀）获取模式串T的next数组值1.我们所知道的KMP算法next数组的作⽤next[j]表⽰当前模式串T的j下标对⽬标串S的i值失配时，我们应该使⽤模式串的下标为next[j]接着去和⽬标串失配的i值进⾏匹配⽽KMP算法的next求值函数我们可以知道next除了j=1时，next[1]为0，其他情况都是⽐较前缀和后缀串的相似度（第三种情况是当相似度为0时，next值为0+1=1）next数组，是⽤来评判前后缀的相识度，⽽next值，则是等于相似度加⼀2.虽然我们知道是⽐较前后缀的相似度，但是我们如何确定前后缀位置来获取next值。

---->pj的next值取决于前缀p1p2....pk-1　后缀pj-k+1.....pj-1 的相似度，next值是相似度加⼀pj的next值取决于前缀p1p2....pk-1　后缀pj-k+1.....pj-1的相似度，是相似度加⼀。

我们将k-1=m,其中m就是相似度，k就是next数组值-->Max{K}pj的next值取决于前缀p1p2....pm　后缀pj-m.....pj-1 的相似度，是相似度加⼀。

那么我们现在的任务，就由找k-1变为找m，找相似度例如：虽然我们可以直接看出abab的相似度是2，也可以编写函数获取到其相似度,⽽且当我们求下⼀个next值时，串变为ababa，这时我们也可以看出相似度为3，使⽤同⼀个函数可以实现获取到相似度。

但是我们这个函数⼤概就是从头或尾开始索引，进⾏判断。

每次我们获取到了⼦串都要交给这个函数从头到尾去索引获取相似度，似乎不划算，我们是不是应该有更好的⽅法增加程序的性能？3.下⾯我们尝试获取下⾯的T串的所有next值，从中找到关联步骤⼀：由上⼀篇博⽂可以知道前j1,j2前两个的next是固定值为0，步骤⼆：获取j=3时的next，此时⼦串只有'ab'，所以⼦串的前缀只能选择'a',后缀只能选择'b';下⾯我们对前后缀进⾏匹配next数组，是⽤来评判前后缀的相识度，⽽next值，则是等于相似度加⼀next[j]表⽰当前模式串T的j下标对⽬标串S的i值失配时，我们应该使⽤模式串的下标为next[j]接着去和⽬标串失配的i值进⾏匹配注意：匹配完毕后后缀会向下加⼀步骤三：获取j=4时的next值，此时⼦串为'aba'，⼦串中前缀是p1..pm,后缀是pm+1..pj-1，若是m取⼀，此时⼦串的前缀可以选择p1，后缀选择p2;若是m=2前缀选择p1p2后缀选择p2p3;那么具体如何选择这个m值呢？重点：这个m值取决于上次失配时的next[]值，即上次j=3是失配了，所有m=next[3]=1,所以我们选取的前缀为p1='a',后缀为pj-1是'a'根据匹配处的相似度或者下标J=1都可以得出next[4]=2步骤四：获取j=5时的next值，此时⼦串为'abab'，⼦串中前缀是p1..pm,后缀是pm+1..pj-1，若是m取⼀，此时⼦串的前缀可以选择p1，后缀选择p2;若是m=2前缀选择p1p2后缀选择p2p3,若m取3，前缀为p1p2p3后缀为p2p3p4;那么具体如何选择这个m值呢？重点：若是上次匹配成功。

kmp算法计算循环字符串（最新版）目录1.KMP 算法简介2.循环字符串的概念及特点3.KMP 算法在循环字符串查找中的应用4.KMP 算法的优缺点分析正文一、KMP 算法简介KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主字符串中查找一个子字符串出现的位置。

该算法的关键在于通过预处理子字符串，减少不必要的字符比较，从而提高匹配速度。

二、循环字符串的概念及特点循环字符串是指一个字符串在到达结尾后，还能继续从某个位置开始重复出现。

例如，字符串"abab"就是一个循环字符串，因为从第四个字符开始，它将重复"ab"的模式。

三、KMP 算法在循环字符串查找中的应用在处理循环字符串的查找问题时，KMP 算法同样具有较高的效率。

它的主要思路是首先预处理循环字符串，构建一个 next 数组，该数组表示子字符串中任意位置的字符与下一个字符之间的最长前缀与后缀相等的长度。

在实际查找过程中，当某个字符匹配失败时，根据 next 数组的值，可以将主字符串的一部分跳过，从而减少匹配次数。

四、KMP 算法的优缺点分析KMP 算法的优点主要体现在对循环字符串的处理上，其时间复杂度在最坏情况下也能达到 O(n)，相较于朴素的字符串匹配算法 O(mn) 有较大的优势。

此外，KMP 算法还具有较好的可扩展性，可以应用于各种字符串处理场景。

然而，KMP 算法也存在一定的局限性。

首先，它需要预处理子字符串，构建 next 数组，这会消耗一定的额外空间。

其次，对于非循环字符串，KMP 算法的性能提升并不明显，因为在最坏情况下，其时间复杂度仍为O(n)。

总之，KMP 算法在处理循环字符串查找问题时表现出较高的效率，是一种值得推荐的字符串匹配算法。

模式匹配的KMP算法详解模式匹配的KMP算法详解模式匹配的KMP算法详解这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法.大概学过信息学的都知道,是个比较难理解的算法,今天特把它搞个彻彻底底明明白白.注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关键就在这里,一般的匹配算法:int Index(String S,String T,int pos)//参考《数据结构》中的程序{i=pos;j=1;//这里的串的第1个元素下标是1while(iababc这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在.这个当T[j]失配后,j应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串无关.《数据结构》上给了next值的定义:0 如果j=1next[j]={Max{k|1aaab->aaab像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢最近的一个,也就是说尽可能的向右滑移最短的长度.OK,了解到这里,就看清了KMP的大部分内容,然后关键的问题是如何求next值先不管它,先看如何用它来进行匹配操作,也就是说先假设已经有了next值. 将最前面的程序改写成:int Index_KMP(String S,String T,int pos){i=pos;j=1;//这里的串的第1个元素下标是1while(i<=S.Length && jT.Length) return i-T.Length;//匹配成功else return 0;}OK,是不是非常简单还有更简单的,求next值,这也是整个算法成功的关键,从next值的定义来求太恐怖了,怎么求前面说过了,next值表达的就是T串的自身部分匹配的性质,那么,我只要将T串和T串自身来一次匹配就可以求出来了,这里的匹配过程不是从头一个一个匹配,而是从T[1]和T[2]开始匹配,给出算法如下:void get_next(String T,int &next[]){i=1;j=0;next[1]=0;while(i<=T.Length){if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}else j=next[j];}}看这个函数是不是非常像KMP匹配的函数,没错,它就是这么干的!注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的,j前面的都匹配的情况下,于是先自增,然后记下来next[i]=j,这样每当i有自增就会求得一个next[i],而j一定会小于等于i,于是对于已经求出来的next,可以继续求后面的next,而next[1]=0是已知,所以整个就这样递推的求出来了,方法非常巧妙.这样的改进已经是很不错了,但算法还可以改进,注意到下面的匹配情况: ...aaac...aaaa.T串中的'a'和S串中的'c'失配,而'a'的next值指的还是'a',那同样的比较还是会失配,而这样的比较是多余的,如果我事先知道,当T[i]==T[j],那next[i]就设为next[j],在求next值的时候就已经比较了,这样就可以去掉这样的多余的比较.于是稍加改进得到:void get_nextval(String T,int &next[]){i=1;j=0;next[1]=0;while(i<=T.Length){if(j==0 || T[i]==T[j]){ ++i;++j;if(T[i]!=T[j]) next[i]=j;else next[i]=next[j];//消去多余的可能的比较,next再向前跳}else j=next[j];}}匹配算法不变.到此就完全弄清楚了,以前老觉得KMP算法好神秘,真不是人想出来的,其实不然,它只不过是对原有的算法进行了改进.可见基础的经典的东西还是很重要,你有本事'废'了经典,就创造了进步.。

kmp算法next原理
KMP算法，全称是Knuth-Morris-Pratt算法，是字符串匹配中一种高效率的算法。

该算法的核心是，利用已经匹配过的部分来减少比较次数。

具体实现是，当出现不匹配时，可以根据已经匹配的前缀和后缀的关系，避免重新匹配已经匹配过的字符，直接跳过这些字符，将模式串向后移动到下一个需要匹配的位置。

那么如何计算这个“已经匹配的前缀和后缀的关系”呢？这就需要用到next数组了。

next数组，本质上是一个数组，用于存储模式串的最长相同真前缀和真后缀的长度。

其中“真前缀”和“真后缀”，是指除了字符串本身的前缀和后缀，即不包含整个字符串的前缀和后缀。

通过预处理模式串生成next数组，我们就可以在匹配过程中根据已经匹配的前缀和后缀的长度，来跳过不必要的比较，从而达到优化匹配速度的目的。

以上就是KMP算法及其核心原理--next数组的简要介绍。

KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。

但是相较于其他模式匹配算法，该算法晦涩难懂，第一次接触该算法的读者往往会看得一头雾水，主要原因是KMP算法在构造跳转表next过程中进行了多个层面的优化和抽象，使得KMP算法进行模式匹配的原理显得不那么直白。

本文希望能够深入KMP算法，将该算法的各个细节彻底讲透，扫除读者对该算法的困扰。

KMP算法对于朴素匹配算法的改进是引入了一个跳转表next[]。

以模式字符串abcabcacab为例，其跳转表为：举例说明，如下是使用上例的模式串对目标串执行匹配的步骤next跳转表，在进行模式匹配，实现模式串向后移动的过程中，发挥了重要作用。

这个表看似神奇，实际从原理上讲并不复杂，对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。

以模式串abcabcacab为例，其前缀4 abca，正好也是模式串的一个子串abc(abca)cab，所以当目标串与模式串执行匹配的过程中，如果直到第8个字符才匹配失败，同时也意味着目标串当前字符之前的4个字符，与模式串的前4个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第5个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。

所以next表的关键就是解决模式串的前缀包含。

当然为了保证程序的正确性，对于next表的值，还有一些限制条件，后面会逐一说明。

如何以较小的代价计算KMP算法中所用到的跳转表next，是算法的核心问题。

这里我们引入一个概念f(j)，其含义是，对于模式串的第j个字符pattern[j]，f(j)是所有满足使pattern[1...k-1] = pattern[j-(k-1)...j - 1](k < j)成立的k的最大值。

KMP算法简析写在前⾯的话：KMP是个套娃算法，主串与⼦串匹配时，若S[i]==T[j] ,两个下标加加就完了；不相等，主串的下标不动，⼦串的下标跳转到前j个⼦串中最⼤重复部分的长度值处。

这个最⼤重复部分（准确的说是最长的相等的真前缀和真后缀）的长度怎么求呢？通过⼀个 next 数组来求得。

这个next数组的获得⼜是在⼦串中进⾏匹配，如果T[k]==T[j]，next[j]=k, j、k 加加就完了，不相等的话不就⼜是回溯嘛？按照原来的⽅法，我们应该将k=0,然后重新⼀个⼀个⽐较寻找重复的⼦串。

但是我们有了next数组了，情况就不⼀样了。

直接让 k 回溯到前 k 个字符中最长重复部分（准确的说是最长的相等的真前缀和真后缀）长度所对应的下标不就好了吗？根据next 数组的含义，不就是next[k] 嘛？让k=next[k] 不就回去了吗纠结什么呢？ 如果你是读者，看到这，你就不应该再看下去了。

除⾮你觉得我上⾯的有问题，可以在评论区骂我。

否则，如果你还是很懵，请到隔壁B站找个视频看看。

算法看博客，真不是个好主意。

⾸先，KMP算法是解决字符串匹配问题的算法，即在主串 S 中查找⼦串 T。

我们从问题⼊⼿，要在主串中查找⼦串，显然可以是⽤蛮⼒法逐个遍历，即从主串的第⼀个字符开始和⼦串的第⼀个字符⽐较，若相等则继续⽐较后续字符，若果不相等，则从主串的下⼀个的字符、⼦串的第⼀个字符重新开始⽐较。

如果在主串遍历完之后还没有找到对应⼦串，则匹配失败。

暴⼒法算法描述如下：public static int findSubString(String s,String t){int i = 0;int j = 0;// 标记主串中开始⽐较的字符下标int index = 0;//如果先主串完了就匹配不成功，⼦串先完了匹配成功。

两者都会结束循环while (i<s.length() && j<t.length()){//这个位置相等，继续下⼀个位置if (s.charAt(i) == t.charAt(j)) {i++;j++;}//这个位置不相等,则从主串的下⼀个字符、⼦串的第⼀个字符重新开始⽐较else{index++;i = index;j = 0;}}//循环结束，判断⼦串是否被匹配完了。

KMP算法解析范文KMP算法的核心是构建一个部分匹配表（Partial Match Table），用来记录已匹配字符串的前缀和后缀的最长公共部分。

这样，在匹配过程中，当出现不匹配的字符时，就可以利用部分匹配表的信息来调整匹配的位置，而不是回溯所有已匹配的字符。

为了方便理解KMP算法的原理，我们首先从部分匹配表的构建开始。

假设待匹配的字符串为P，原字符串为T。

1.部分匹配表的定义：部分匹配表是一个长度为P.length的数组，记为next[]，其中next[i]表示长度为i的前缀子串（不包含最后一个字符）和后缀子串（不包含第一个字符）的最长公共部分的长度。

2.部分匹配表的构建：首先，next[0]被定义为-1，next[1]被定义为0。

然后，从i=2开始，依次计算next[i]的值。

（1）假设next[i-1]的值已经求得，即长度为i-1的前缀子串和后缀子串的最长公共部分的长度为next[i-1]。

（2）将P的前缀子串P[0:i-1]和后缀子串P[1:i-1]的长度都加1，得到长度为i的前缀子串和后缀子串。

分别记为P[0:i]和P[1:i]。

（3）比较P[0:i]和P[1:i]，找到最长的公共部分。

如果存在公共部分，则next[i]取公共部分的长度；否则，next[i]取0。

其中，比较的方法是利用已经求得的next[i-1]和P[i-1]来确定比较的位置。

具体而言，如果P[i-1]与P[next[i-1]]相等，则next[i]等于next[i-1]加1；否则，需要继续往前寻找可能的公共部分，即比较P[i-1]和P[next[next[i-1]]]，直到找到公共部分或者找到P的开头。

3.KMP算法的匹配过程：假设待匹配的字符串为P，原字符串为T，分别用变量i和j表示匹配过程中的位置。

（1）初始化i=0和j=0。

（2）比较P[i]和T[j]。

如果相等，则继续比较下一个字符；如果不相等，则根据部分匹配表调整i和j的值。

KMP算法详解(C++版)KMP算法是一种字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）.KMP 算法之所以难懂，很大一部分原因是很多实现的方法在一些细节的差异。

然后去看另外的方法，就全都乱了！体现在几个方面： next 数组，有的叫做“失配函数”，其实是一个东西； next 数组中，有的是以下标为 0 开始的，有的是以 1 开始的； KMP 主算法中，当发生失配时，取的 next数组的值也不一样！就这样，各说各的，乱的很！所以，在阐述我的理解之前，我有必要说明一下，我是用 next 数组的， next 数组是以下标 0 开始的！还有，我不会在一些基础的概念上浪费太多，所以你在看这篇文章时必须要懂得一些基本的概念，例如“朴素字符串匹配”“前缀”，“后缀”等！假设在我们的匹配过程中出现了这一种情况：根据 KMP 算法，在该失配位会调用该位的 next 数组的值！在这里有必要来说一下 next 数组的作用！说的太繁琐怕你听不懂，让我用一句话来说明：返回失配位之前的最长公共前后缀！好，不管你懂不懂这句话，我下面的文字和图应该会让你懂这句话的意思以及作用的！首先，我们取之前已经匹配的部分（即蓝色的那部分！）我们在上面说到 next 数组的作用时，说到“最长公共前后缀”，体现到图中就是这个样子！接下来，就是最重要的了！没错，这个就是 next 数组的作用了 :返回当前的最长公共前后缀长度，假设为 len 。

因为数组是由 0 开始的，所以 next 数组让第 len位与主串匹配就是拿最长前缀之后的第 1 位与失配位重新匹配，避免匹配串从头开始！如下图所示！（重新匹配刚才的失配位！）如果都说成这样你都不明白，那么你真的得重新理解什么是 KMP 算法了！接下来最重要的，也是 KMP 算法的核心所在，就是 next 数组的求解！不过，在这里我找到了一个全新的理解方法！如果你懂的上面我写的的，那么下面的内容你只需稍微思考一下就行了！跟刚才一样，我用一句话来阐述一下 next 数组的求解方法，其实也就是两个字：继承a 、当前面字符的前一个字符的对称程度为 0 的时候，只要将当前字符与子串第一个字符进行比较。

KMP算法详解写在前⾯：欢迎转载，转载请在⽂章显眼处注明出处：https:///grcyh/p/10519791.html起源所谓KMP(看⽑⽚233⼿动滑稽)算法，就是⼀种改进的算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此⼈们称它为————操作（简称KMP算法）。

KMP算法的关键是利⽤匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的⽬的。

具体实现就是实现⼀个next()函数，函数本⾝包含了模式串的局部匹配信息。

O(m+n)。

——百度百科前置知识：输⼊输出数组for循环模式串匹配的概念：模式串匹配，就是给定⼀个需要处理的⽂本串和⼀个需要在⽂本串中搜索的模式串，查询在该⽂本串中(⼀般⽂本串应远⼤于模式串)，模式串的是否出现过，出现的次数和出现的位置等。

朴素算法：⾸先要理解，朴素的单模式串匹配⼤概就是枚举每⼀个⽂本串元素，然后从这⼀位开始不断向后⽐较，每次⽐较失败之后都要从头开始重新⽐对，那么如果模式串和⽂本串是类似于这样的：模式串aaaab，⽂本串是aaabaaabaaab，如果是这样的话，我们设模式串长度为m，⽂本串长度为n，那么朴素的暴⼒算法就会被卡成O(nm)，于是就有了那三个家伙⼤佬的KMP(然⽽并不认识他们是谁233)，下⾯我们就要讲KMP了，准备好！KMP：在朴素算法中，我们每次匹配失败都不得不放弃之前所有的匹配进度，因此时间复杂度很⾼，⽽KMP算法的精髓就在于每次匹配失败之后不会从模式串的开头进⾏匹配，⽽是根据已知的匹配数据，跳回模式串⼀个特定的位置继续进⾏匹配，⽽且对于模式串的每⼀位，都有⼀个唯⼀的“特定跳回位置”，从⽽节约时间。

⽐如我们考虑⼀组样例：模式串：abcab⽂本串：abcacababcab⾸先，前四位按位匹配成功，遇到第五位不同，⽽这时，我们选择将模式串向右移三位，或者可以理解为移动到模式串中与失配字符相同的那⼀位。