2024年10月kmp算法视频讲解（数据结构与算法——字符串匹配问题(KMP算法)）

　　⑴kmp算法视频讲解（数据结构与算法——字符串匹配问题(KMP算法)

　　⑵数据结构与算法——字符串匹配问题(KMP算法)

　　⑶KMP算法也是比较著名的模式匹配算法。是由D.E.Knuth,J.H.Morrs和VR.Pratt发表的一个模式匹配算法。可以大大避免重复遍历的情况。

　　⑷如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母“f“和“x“不相等。如下图：

　　⑸T=“abcdex”j模式串abcdexnext

　　⑹T=“abcabx“j模式串Tabcabxnext

　　⑺T=“ababaaaba“j———————模式串T———ababaaabanext————

　　⑻T=“aaaaaaaab“j———————模式串T———aaaaaaaabnext————

　　⑼next数组其实就是求解字符串要回溯的位置假设，主串S=“abcababca”;模式串T=“abcdex”，由以上分析得出next数组为，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

　　⑽KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T=“aaaaax”。next的数组就是；

　　⑾当开始匹配时，当i=，j=时，我们发现字符“b“与字符“a”不相等，如上图，j=next=;

　　⑿由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next,那么next数组为{,,,,,};

　　⒀在求解nextVal数组的种情况

　　⒁kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法。KMP算法的关键是根据给定的模式串W,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。完全掌握KMP算法思想学过数据结构的人，都对KMP算法印象颇深。

　　⒂怎样简单明了的解释KMP算法

　　⒃map根据输入的映射函数，将一个集合映射为另一个集合，比如：输入集合为{,,,,}，输入的函数为f(x)=x^，那么输出的集合就是{,,,,}。reduce就是根据输入的归约函数，将集合（一般指map输出的集合归约，比如上面的输出集合是{,,,,}，假设我们的归约函数是f(x,y)=x+y,那么reduce的过程就是{,,,}-》{,,}-》{,}-》{}。我们使用Java来描述这个过程：intresult=IntStream.range(,)//获得集合{,,,,}.map(x-》x*x)//映射为{,,,,}.reduce((x,y)-》x+y)//归约.getAsInt();//获得结果System.out.println(result);结果：

　　⒄大一下参加学校ACM预备队集训的时候首次接触KMP算法，当时看了很多介绍文章，仍然不是很理解其实质，只是简单地套模板AC题目，待大二数据结构与算法课堂上再听老师介绍一次，才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢？正巧最近和朋友聊天时他告诉我他对KMP不是很理解，于是打算自己写一篇文章，巩固自己对KMP的认识，也希望能够帮助更多朋友理解KMP。在开始之前，需要知晓的概念：

　　⒅前缀：以原串串头为自身串头的子串，如的前缀有：后缀：以原串串尾为自身串尾的子串，如的后缀有：

　　⒆注意：字符串前后缀都不包括该串本身

　　⒇给你一个文本串T(TextString)

　　⒈再给你一个模式串P(PatternString)

　　⒉问该模式串是否在文本串中，怎么找？

　　⒊一开始只好分别从文本串与模式串的串头开始逐字母比较

　　⒋二者相同，再比较T串与P串的下一位

　　⒌如果一直这么顺利，两串对应位置的字符总相同，待P串中最后一个字符也匹配完毕，说明该模式串在文本串中存在，耶(??ω??)y超开心，查找结束。但，大多数匹配过程不会如此顺利，在该例中，当匹配进行至

　　⒍很明显，失配了。现在怎么办？按朴素思想，将P串相对T串整体右移一位，重新开始匹配，即

　　⒎但这种算法效率无疑是十分低下的。设T串长度N，P串长度M，则朴素算法时间复杂度为O(MN)

　　⒏已知的重要信息并没有被使用——已匹配的字符串前缀

　　⒐在上例中，当P串最后一个字符匹配失败时，其已有包含七个字符的前缀子串S匹配成功

　　⒑完全可以利用前缀子串S做点什么。观察到在S串

　　⒒中，有相同前后缀，即下图蓝色部分

　　⒓而S串各字符又与T串中对应字符相同，即有

　　⒔当失配发生后，直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分

　　⒕从图中红框部分继续尝试匹配，发现再次失配。这次，已匹配成功的前缀串S为

　　⒖而在该串中没有相同的前后缀，只能将P串串头移至失配处进行比较

　　⒗再次失配。此时前缀串S为空串，只好如朴素算法般将P串整体右移一位，重新开始比较

　　⒘匹配成功。于是又按照之前的步骤往下匹配，直至再次失配或匹配成功

　　⒙后续步骤同上，不再赘述

　　⒚上述示例已展现，KMP算法的精髓在于对已匹配成功的前缀串S的利用

　　⒛在朴素算法中，匹配失败了，T串待匹配字符会回溯

　　T串原本已匹配至T=’b’重新开始匹配

　　而在KMP算法中，若P早已匹配过，何必再回溯过去重复匹配呢？于是乎，就如问题引入部分展示般

　　每当失配发生，我们总是去关注P串中已匹配成功的前缀串S

　　因为该前缀串是匹配成功的，说明在T串中必定存在与该前缀串相同的子串，记为S’

　　若S串中存在相同前后缀

　　则S’串必然也存在此相同前后缀

　　所以只需将P串右移四位，使得S串的该相同前缀对齐S’串的该相同后缀

　　至于T是否能够匹配另说（当然，本例中一看就知道没匹配上，但通过对前缀串S的利用，成功省去了P串右移一位、两位和三位后的无效匹配

　　继续深入思考，给定一个具体的P串，其第N位的前缀串S内容是固定的，则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之，对于一个具体的P串，当其与给定T串匹配至P失配后，应当使用N之前的哪一位再来与T串进行匹配，以此提高匹配效率，记该数组为Next数组

　　定义Next=j表示当P串中第i位失配后，跳转至P串第j位再次尝试匹配

　　还是以之前的P串为例，它的Next数组求出来应为

　　取下标为例，其前缀串为

　　若P=，其余下标对应Next数组值同如此求。

　　特别地，规定Next的含义是前N-个已匹配成功的字符构成的前缀串S中，最长相同前后缀长度。所以若在下标为N处匹配失败了，则应前往Next所对应的下标处匹配。

　　具体地，以下图所示为例，P失配

　　当求出P串Next数组后，便可快速进行与T串的匹配

　　现在问题只剩下如何求Next数组，注意到Next数组既然只与P串本身相关，与文本串T无关，故令P串与自身匹配即可求得

　　令其与给定文本串相匹配

　　失配，于是跳转至P处再次尝试匹配

　　再度失配，也必然失配

　　本例中该字符串新Next数组为

　　失配，于是跳转至P处再次尝试匹配

　　省去了之前跳转至P处的无效匹配

　　设T串长度M，P串长度N，由于KMP算法不会回溯，分析易知时间复杂度为O(m+n)

　　对于P可以取至n中任意值，为最大化匹配效率考虑，总是取最大相同前后缀以提高效率，节省时间

　　KMP模式匹配算法KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明。求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数。include“string.h“#include《assert.h》intKMPStrMatching(StringT,StringP,int.N,intstartIndex){intlastIndex=T.strlen()-P.strlen();if((astIndex-startIndex)《)//若startIndex过大,则无法匹配成功return(-);//指向P内部字符的游标inti;//指向T内部字符的游标intj=;//指向P内部字符的游标for(i=startIndex;i《T.strlen();i++){while(P&&j》)j=N;if(P)j++;if(j==P.strlen())return(-j+);//匹配成功,返回该T子串的开始位置}return(-);}

　　KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next中最长后缀的长度等于相同字符序列的前缀。对于next数组的定义如下：)next=-j=)next)next=其他如：Pababajnext-即next因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next=-，则将i右移位，并将j置，继续进行比较。

　　一种由Knuth(D.E.Knuth)、Morris(J.H.Morris和Pratt(V.R.Pratt三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n，只用到辅助函数π的值包含了与a无关但在计算δ（q，a时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。

　　KMP算法真的好难懂啊哪位高手来讲解一下谢谢！

　　额这个问题之前没多久给别人解答过，我就直接搬过来了……————————————————————————————————————————好吧~KMP当初我也想了挺久的~很巧妙的算法啊！相必复制百科什么的你也不会看的了所以我手打吧…下面是我的理解~为了解说方便我把长的称为文本串，短的称为目标串~常规的匹配算法是把目标串一位一位地右移，跟文本串比较，而KMP则是跳着右移~举几个例子相信你就懂了————————————————————————————————————————比如有一目标串为ababaca，当前位置匹配了前个，也就是匹配了ababa，后面两个不匹配这说明了文本串当前位置也是ababa显然右移一位是不行的，因为从目标串可以看出(abab)a与a(baba)括号里的内容不相等而右移两位是可能可行的~因为可以看出(aba)ba与ab(aba)括号里的内容是相等的，这意味着移动两位后，目标串前三位aba是肯定匹配的~因为移动前也匹配~————————————————————————————————————————再举一个例子~比如有目标串abcab，当前位置匹配了前两个ab那么就需要右移个位置，因为(ab)cab与abc(ab)括号里内容相同，移动后有可能会匹配~————————————————————————————————————————懂了么？表达能力有限…我也不能讲得更好了…具体代码网上一大堆，《算法导论》里面也有~我当初就是在算导里学会的！如果懂了，希望有追加分啊，手打累死！！！不懂的话，追问吧……