公司网站上的员工风采怎么做,网站app在线制作,网站后期维护协议,服装网站策划设计前言#xff1a; 在一些寻找子串的问题中#xff0c;我们常常使用的是BF算法#xff0c;也就是暴力算法#xff0c;这样做的时间复杂度通常都是O(N^2)#xff0c;且不能体现出算法的美妙之处#xff08;虐人之处#xff09;#xff0c;于是三位大佬D.E.Knuth#xff0…前言 在一些寻找子串的问题中我们常常使用的是BF算法也就是暴力算法这样做的时间复杂度通常都是O(N^2)且不能体现出算法的美妙之处虐人之处于是三位大佬D.E.KnuthJ.H.Morris和V.R.Pratt提出了一种船新的方法时间复杂度真的很低 O(nm),这个算法由三位大牛的名字首字母来命名也就是我们今天的主角KMP算法。 我将KMP算法的详解分为三个篇章 -【原理篇】主要讲解KMP实现的原理以及手动求NEXT数组。 【数理篇】主要讲解如何在手动求出NEXT数组的情况下找出数学规律为之后的算法实现奠定基础。 【实现篇】主要讲解以C语言代码的方式实现KMP算法以及NEXT数组的优化。 其余篇章将在之后更新 制作不易若对你有帮助的话点赞、关注、评论走一波你们的支持是我前进路上最大的动力。 实现原理 当你有两个字符串DES目标字符串和PAT模板字符串你要去DES中寻找是否有子字符串与模板串PAT相同。 BF也就是暴力算法的实现思路是这样的当DES[i]PAT[j]的时候先记录此时的I下标令cntI,之后执行IJ。若DES[i]!PAT[j]的时候I回退到起始下标也就是cnt的位置j回退到PAT字符串的首位也就A(0)的位置 聪明的你一定发现这样做会导致i和j一直往回走效率实在不高有没有可能让j有规律的回退而i一直向前呢
KMP算法就是这样做的
试想一下当i与j分别指向这的时候表示前三个字符都匹配上了接下来我们按照BF算法的思路让ij向后移动一格。 这时候DES[i]所指向的字符为A而PAT[j]所指向的字符为C按照BF的思路此时i j都需要执行一个回退的操作。但你们仔细观察看看j能指向C是否能说明前三个元素AAA是DES中前四个元素的一个子串 也就是说PAT的AAA一定在DES中能被匹配上不然J也无法移动到这了。 那我们这时候还需要将J回退到最开始的位置吗我们不需要了我们只需要将j移动到PAT数组中以PAT[0]为首PAT[j-1]为结尾的两个子字符串的长度位就可以了。听不懂没关系底下我会介绍这种算法 例如AAA以第一个A为首中间的A为尾是第一个子字符串以中间的A为首最后一个A为尾是第二个子字符串这两个子字符串的长度为22为长度位这时将J移动到PAT中下标为2的地方。 但你不禁会想为什么要这么退呢因为你退回的是DES中匹配过的所有的字符的子字符串。这是一个难点可以自己多举几个例子想想。若没听懂也可以先接着往下看影响不大。 这也就是KMP算法当中的核心之处NEXT数组。 NEXT数组 在前面我们已经简单体会到了NEXT数组可以用这么一句话来概括NEXT数组的作用 指导PAT中的j要回退到PAT中的哪一个位置。NEXT[j]存储了从PAT[0]到PAT[j-1]位置以PAT[0]为首PAT[j-1]为结尾的两个最长子字符串的长度位可以重叠但不能相等。 那么我们怎么来求NEXT数组呢别急接下来我会举两个例子。
EX1
012345678910PAT字符串abcababcabcNEXT数组-10001212345 我们规定NEXT[0]-1 NEXT[1]0.(有些地方的定义不一样但这没关系在代码中做相应修改就可以了)从NEXT[2]开始我们需要自己算。 牢记我们的口诀NEXT[j]以PAT[0]为首PAT[j-1]为结尾的两个最长子字符串的长度位可以重叠但不能相等。 我们看看NEXT[2]中是否满足呢首a 尾b显然没有以a为首b为尾的字符串那么我们就在这里填上0也就是NEXT[2]0 NEXT[3]首a 尾c显然也没有以a为首c为尾的两个子字符串所以NEXT[3]0; NEXT[4]首a 尾apat[0]a,pat[3]a找到了两个子字符串就是首尾本身他们有多长呢显然是长度1所以NEXT[4]1 NEXT[5]首a 尾bpat[0-1]ab,pat[3-4]ab这里表示下标3到下标4下同找到了两个子字符串以PAT[0]为首PAT[45-1]为尾的两个字符串长度为2所以NEXT[5]2 NEXT[6]首a 尾apat[0]a,pat[5]a找到了两个字符串就是首尾本身他们有多长呢显然是长度1所以NEXT[6]1 NEXT[7]首a 尾bpat[0-1]ab,pat[5-6]ab找到了两个子字符串以PAT[0]为首PAT[67-1]为尾的两个字符串长度为2所以NEXT[7]2 NEXT[8]首a 尾cpat[0-2]abc,pat[5-7]abc找到了两个子字符串以PAT[0]为首PAT[78-1]为尾的两个字符串长度为3所以NEXT[8]3 NEXT[9]首a 尾apat[0-3]abca,pat[5-8]abca找到了两个子字符串以PAT[0]为首PAT[89-1]为尾的两个字符串长度为4所以NEXT[9]4 NEXT[10]首a 尾bpat[0-4]abcab,pat[5-9]abcab找到了两个子字符串以PAT[0]为首PAT[910-1]为尾的两个字符串长度为5所以NEXT[10]5 到此该PAT的next数组已经告一段落。下面还有一个例子我直接给出了答案若还是没懂可以对照上面的方法进行求解或评论私信问我都可。
012345678910PAT数组abcababcabcNEXT数组-10001212345 至此本篇博客的内容九分钟带你弄懂KMP算法【原理篇】告一段落若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
