学习
实践
活动
专区
工具
TVP
写文章

KMP

简介 KMP 算法是一种优秀的字符串模式匹配算法,相对于暴力匹配方法来说,其改进在于:每当一趟匹配过程出现字符比较不相等时,不需回溯主串的 iii 指针,而是利用已经得到的「部分匹配」的结果将模式串向右 设 则失配数组的计算公式如下: 计算失配数组时间复杂度 ,主串与模式串匹配时间复杂度 ,故 KMP 算法总的时间复杂度为 。 3. 模板 #include <bits/stdc++.h> using namespace std; #ifndef _KMP_ #define _KMP_ #define ll int #define MAXN 1000005 #define MAXM 1000005 // KMP 算法 struct KMP { // 失配数组 // next[j] 表示当模式中第 j 个字符与主串字符失配时 // 模式串中失配位置需要滑动到的位置 ll next[MAXM]; vector <ll> match; KMP() {} // 计算失配数组

10210
  • 广告
    关闭

    热门业务场景教学

    个人网站、项目部署、开发环境、游戏服务器、图床、渲染训练等免费搭建教程,多款云服务器20元起。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    KMP(1)

    第3~5行是枚举L=2, 3, 4时的匹配过程,都是第一个字符就失配了;第6行是L=5时的匹配过程,第一个字符a匹配上了,第二个字符失配了 KMP算法  首先我们定义一个函数:失配位置f(x)。 在上面的例子中,f(1)=6, f(2)=2, f(3)=3, f(4)=4, f(5)=6  KMP算法的优化思路就是,枚举L的过程中,跳过使失配位置减少的L。 所以在P[K+1]失配时,KMP的思路是,找一个最小的d满足P[1..K-d]==P[1+d..K]  形象的说也就是找到P[1..K]的一个最长前缀,并且这个前缀同时也是P[1..K]的一个后缀,也就是 K+1]与S[x+K]失配时 通过将P[next[K]]对准S[x+k-1],实现跳过使失配位置减少的L 继续比较P[next[K]+1]与S[x+K],而不用从P[1]开始比较  有了next数组,KMP [j + 1]) j = next[j] j = j + 1 if(j == P.len) return i - P.len + 1 }  用图示来展示KMP

    23730

    重学KMP

    思路 本题是KMP 经典题目,通过道题题目我们把来把KMP彻底讲清楚。 以下文字如果看不进去,可以看我的B站视频,再结合本篇文章来看,相信可以解决你对KMP算法的所有疑惑! 本篇将以如下顺序来讲解KMP, 什么是KMP KMP有什么用 什么是前缀表 为什么一定要用前缀表 如何计算前缀表 前缀表与next数组 使用next数组来匹配 时间复杂度分析 构造next数组 使用next 数组来做匹配 前缀表统一减一 代码实现 前缀表(不减一)代码实现 总结 什么是KMP 说到KMP,先说一下KMP这个名字是怎么来的,为什么叫做KMP呢。 所以叫做KMP KMP有什么用 KMP主要应用在字符串匹配上。 KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。 所以如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任。 其实KMP的代码不好理解,一些同学甚至直接把KMP代码的模板背下来。 没有彻底搞懂,懵懵懂懂就把代码背下来太容易忘了。

    20320

    KMP(3)

    如果没有满足条件的位置K就输出-1  这其实就是一个整数版的KMP。我们之前讲KMP的背景都是字符串匹配,其实也可以拿来做数组序列匹配。 第二个思路需要对KMP的理解更加清楚,才能更加灵活的运用 例4 题目链接:hihoCoder1625 ?  题目大意是给定两个字符串A和B,请你求出字符串A最少重复几次才能使得B是A的子串。 如果没有解输出-1  这题降低时间复杂度的关键是一次性得到足够长的S,进行KMP;而不能从一个比较短的S开始尝试KMP,匹配不成就在S后面接一个A,再匹配不成再接一个A……  于是问题来了,S多长才是足够长 当我们KMP的过程中需要用的S[i]的时候,就用A[(i-1) % A.len+1]代替。 这道题目的大意是给定两个字符串P和S,让你找一个最长的字符串T满足T是P的前缀,也是S的后缀  如果你对KMP的过程非常清楚的话,你会发现KMP用P去匹配S的过程中,如果S[i]匹配上了P[j]那就说明

    289100

    KMP算法

    $j$表示指向$P$的下标),由于失配,按照暴力做法,下一步的比较是下面这样的: S: ABCDABCDABDE P: ABCDABD 此时$i=1$,$j=0$重新开始比较 KMP next[j]$表示字符串$P$的长度是$j$的前缀的前缀和后缀相等的最大长度 P:ABCDABD next:-1 0 0 0 0 1 2 0 如何求解next数组: 求解$next$数组的代码 void kmp_pre -1] = P[next[n]…n-1]$ 相关题目练习: 1.POJ3461 题目描述: 给$t$组数据,每一组数据给两个字符串$W$和$T$,求字符串$W$在字符串$T$的出现次数 题解: 直接上kmp 有两个序列一个是长度为$n$的数字序列$a$,一个是长度是$m$的数字序列$b$,求最小的$k$使得$a[k…k+m-1] = b[1…m]$ 题解: 就是求$b$在$a$中第一次出现的位置,直接上kmp kmp的$next$数组简直就是米奇妙妙屋 #include <bits/stdc++.h> using namespace std; typedef long long LL; #define dbg

    21920

    KMP(2)

    如果不优化会成为整个KMP的瓶颈,导致还不如直接用O(P.len * S.len)的暴力算法匹配效率高。要优化求next数组的算法,就需要对next数组有深入的理解。 = P[j] j = next[j] Next[i] = ++j  下面看一下KMP求匹配的完整代码: #include <cstring> #include <cstdio> 第23-33行是在进行KMP匹配。注意其中第28-32行,如果匹配已经进行到j==m,说明P的最后一个字符P[m]也匹配上了,并且匹配到的是S[i]。 需要注意出现的P是可以部分重叠的,比如ADA在ADADADA中出现了3次  之前KMP的代码是找到第一次出现的位置就中止了。现在我们需要让KMP在找到一次完整的匹配之后还能继续匹配下去。 ,所以为了提交到hihoCoder上不会编译出错,我们把next[]数组的名字改成nxt[]  然后就是第31-35行,这里匹配到j==m说明完成了一个完整匹配之后,我们令j=nxt[j],就可以让KMP

    19340

    hihoCoder #1015 : KMP算法【KMP裸题,板子】

    #1015 : KMP算法 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进 可以使用KMP算法进行求解!“ 河蟹满意的点了点头,对小Hi说道:”既然你知道就好办了,你去把小Ho教会,下周我有重要的任务交给你们!“ ”保证完成任务!”小Hi点头道。 提示一:KMP的思路 提示二:NEXT数组的使用 提示三:如何求解NEXT数组 输入 第一行一个整数N,表示测试数据组数。 接下来的N*2行,每两行表示一个测试数据。 44 */ 45 inline int kmp_index() 46 { 47 int i=0,j=0; 48 getnext(); 49 while(i<slen&& i-tlen; 61 else 62 return -1; 63 } 64 /* 65 返回模式串在主串S中出现的次数 66 */ 67 inline int kmp_count

    48150

    扫码关注腾讯云开发者

    领取腾讯云代金券