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

算法字符串KMP模式匹配

在朴素的模式匹配算法中,主串的pos值(i)是不断地回溯来完成的(见字符串的基本操作中的Index函数)。而计算机的大仙们发现这种回溯其实可以是不需要的。 下面摘录一段阮一峰所写关于kmp的文章,增进理解: ? 因为空格与C 不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。 */ int IndexKMP(String Src, String Sub, int pos) {     cout << "KMP Index ..." << endl;     int i = pos  next);*/     GetNextVal(Sub, next);     while (i < len1 && j < len2)     {         /* 两字母相等则继续,与朴素算法增加了

70780

KMP 模式匹配算法

由三位前辈发表的一个模式匹配算法,可以大大避免重复遍历的情况,称之为克努特-莫里斯-普拉特算法,检查 KMP 算法。 又叫 快速模式匹配算法KMP 算法相比于 BF 算法,优势在于:在保证指针 i 不回溯的前提下,当匹配失败时,让模式串向右移动最大的距离; 并且可以在 O(n+m) 的时间数量级上完成对串的模式匹配操作。 KMP 算法原理参考链接:CSDN nextval[1] = 0;   int j = 0;   while (i<strlen(str)) @version v1.0 * @copyright T 有部分相同子串时,可以简化朴素匹配算法中的循环流程 湖北遴选从子串最长前缀和最长后缀开始求。 于模式串中的某一字符来说,提取它前面的字符串,分别从字符串的两端查看连续相同的字符串的个数,在其基础上 +1 ,结果就是该字符对应的值。

19820
  • 广告
    关闭

    热门业务场景教学

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

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

    字符串匹配KMP算法

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特—莫里斯—普拉特算法KMP算法主要分为两个步骤:字符串的自我匹配,目标串和模式串之间的匹配。 ? KMP.jpg (一)字符串的自我匹配 所谓字符串的自我匹配,就是看字符串中左右侧相等的最长子串的字符个数。 实际上selfMatch也相当于两个字符串之间的匹配,只不过模式串是被包含在目标串中的子串罢了。 假如复杂度是mn的话,那么这个KMP算法相对于BF算法就谈不上改进了。 分析一下这个while循环,实际上它的作用就是让j不断变小,导致p串不断右移。 显然,在i=0到i=n-1的整个比较过程中,j最多只能往右挪移n次,所以while循环的平均复杂度最多为1,所以KMP算法是线性的,复杂度是n,而不是mn。这就是KMP算法存在的价值。

    1.3K100

    KMP字符串匹配算法

    KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人提出的一种快速模式匹配算法 算法的演变 我们由上面KMP朴素算法的例子来引出一个问题。 我们再深入分析,转换思考问题的侧重点,发现5位字符正好是P(Pattern)子串的长度,是不是P子串本身就蕴含了模式匹配的奥秘? 答案是肯定的! KMP算法 KMP算法,是由KMP朴素算法演变而来的,主要分为两步: 第一步,当字符串比较出现不等时,确定下一趟比较前,应该将子串pattern右移多少个字符(预处理) 第二步,子串pattern右移后 总结: 第一步,其实就是KMP朴素算法模式匹配子串pattern的预处理过程,上面已经给出了算法公式和代码示例 第二步,本质上就是KMP朴素算法,不同的仅仅是pattern右移的位数大小由其预处理过程决定

    67210

    KMP 字符串匹配算法

    KMP(Knuth-Morris-Pratt) 算法是一种常见的字符串匹配算法,在主字符串 S 中查找字符串 M 出现的起始位置,通过 M 的自身信息来减少无效的查询次数。 ,从 S 的第一个字符开始的 len(M) 个字符串与 M 进行匹配,如果匹配成功则返回位置,如果不成功则从 S 的第二个字符开始的 len(M) 个字符串与 M 进行匹配,循环向后进行匹配判断,直到剩余的字符串长度小于 KMP算法 在了解KMP算法之前,首先看两个貌似无关的概念:前缀和后缀。前缀是指除最后一个字符或多个字符的字符串组合,后缀是指除第一个字符或多个字符的字符串组合。 KMP算法中查找 M 在 S 中位置,在匹配过程中,通过分析 M 与 S 的已匹配字符串信息来避免回退现象,过程如下: 从 S 的第一个字符开始进行逐个扫描对比: ? KMP 算法保证了 i 指向的 S 中位置不需要进行回退,可以减少无效的回退造成的性能浪费。

    71630

    KMP字符串匹配算法

    KMP算法是很经典的字符串匹配算法,在字符的匹配过程中,只要遍历一次就可以找出所有的匹配串。对于超大型字符串来说,是一种非常高效的算法KMP算法的核心是next数组。 next数组就是在遇到不匹配的字符时,匹配串应该从哪些一个字符开始与被匹配串开始进行比较。 简单来说就是匹配串中哪些是重复出现的,记住这些重复出现的位置,重复的字符就不要比较了,从下一个不匹配的字符开始比较就可以。 下面举例来说明一下next数组 以字符串st= “stst1” 为例, next数组初始为[0,0,0,0,0]。 可以看到 s[0]=s[2], 对于如果s[3]位置不匹配时,只需要从比较s[1]的位置,因此next[3]=1。

    17340

    字符串匹配算法KMP

    KMP由来 上一节说的BM算法是最高效、最常用的字符串匹配算法。 最知名的却是KMP,它3位作者(D.E.Knuth,J.H.Morris,V.R.Pratt),算法的全称是Knuth Morris Pratt 算法,简称KMP算法。 2. KMP算法基本原理 类似于BM里的概念:坏字符(不能匹配的),好前缀(已经匹配的那段) ? ? KMP算法目的:当遇到坏字符后,对于已经对比过的好前缀,将模式串多滑动几位 ? 上面可以看出,可以事先预处理好模式串,与主串比较时,直接用next数组 构建next数组(失效函数) next 数组含义:当前字符之前的字符串(不含当前)中,最大长度的相同前缀后缀子串。 代码 王争的代码不好理解,找了书和别的人的代码参考 /** * @description: KMP字符串匹配算法 * @author: michael ming * @date: 2019/6/22

    18910

    算法 | KMP字符串匹配

    字符串是不可变数据类型,也就是说你要改变原字符串内的元素,只能是新建另一个字符串字符串匹配就是基于最简单的字符比较,其中的模式串就是普通字符串,所做匹配是在目标串里查找等于模式串的子串。 也就是说,比较的一方是表示模式字符串,另一方是目标字符串的所有可能子串。我们常用的就是朴素的串匹配算法和无回溯串匹配算法KMP算法)。 2. 则可以认为模式P在T中出现过。 (1) 朴素的串匹配算法 最简单的朴素匹配算法采用最直观可行的策略: (1)从左到右逐个字符匹配;(2)发现不匹配时,转去考虑目标串里的下一个位置是否与模式匹配。 (KMP算法) 在状态(0)匹配到第一个c失败时,由于已知前两个字符不同,KMP算法直接把模式串移两个位置,模式串开头的a移到c匹配失败的位置,达到状态(1)。 KMP算法直接把模式串的b移到刚才匹配c失败的位置(前面字符a肯定匹配,不必再试),达到状态(2)。接下去从模式串的b继续匹配,找到了一个成功匹配

    44720

    字符串匹配KMP算法

    关于字符串匹配KMP算法其实不难,只要理解字符串下一步匹配需要移动的个数就可以了,但是说是这么说,实际理解肯定会有或多或少的问题,要是大家看完之后还是有问题有疑问的同学,可以再文章底部加我~ 字符串匹配KMP算法 字符串匹配是计算机的基本任务之一。 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。 ? 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。 1. ? 一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

    71340

    字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? ? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。 ? 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。 1. ? 因为B与A不匹配,搜索词再往后移。 3. ? 就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。 4. ? 接着比较字符串和搜索词的下一个字符,还是相同。 5. ? 一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

    66360

    KMP算法(字符串匹配问题)

    注意,是KMP算法,不是MMP哈,我没有骂人。KMP算法是用来做字符串匹配的,除了KMP算法分,还有暴力匹配算法,也是用来做字符串匹配的。接下来先看看暴力匹配算法,你就知道为啥会出现KMP算法了。 算法思路: 假如现有两个字符串: String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; 假设现在str1匹配到i位置,str2 介绍: KMP算法,是一个判断字符串是否在另一个字符串中出现过的算法,如果出现过,返回最早出现的位置。 和暴力匹配算法不同的是,KMP算法会用一个next数组来保存字符串中前后最长公共子序列的长度,每次回溯时,通过next找到前面匹配过的位置,这样就省了大量的时间。 2. KMP算法使用步骤: 首先得到匹配串的部分匹配表; 利用部分匹配表进行匹配; 5.

    16520

    字符串匹配算法KMP

    不再列举了,面对产品经理各种需求大家尽情发挥脑洞吧,那么开始进入今天的正题,溪源采用KMP字符串匹配算法解析此需求。 基础知识 根据上面介绍的需求,大家应该会对KMP算法解决的问题稍有理解。 KMP算法解决的问题:在字符串(主串)中是否能够定位出模式串(子串)。 上面提及到暴力匹配字符串,为什么不使用呢?时间复杂度O(m*n),而KMP算法时间复杂度为O(m+n)。 ABCDABCDABDE"的第一个字符与搜索串(模式串,以下简称P串)"ABCDABD"的第一个字符,进行比较。 从5点可以明确知道,P串中字符D与主串空格不匹配时,其实字符D之前已经匹配的六个字符是已知的。因此KMP算法思想就是利用这个已知信息,不要重复比较已经比较过的位置,而是继续将P串向后移动几位。 源码实现 public class Kmp { /** * * @param originString 源字符串 * @param subString 子串

    32630

    KMP模式匹配算法-串的应用

    那么废话不多说,让我们进入今天的主题叭~数据结构之串及其应用KMP模式匹配算法。 即串的模式匹配。 ? 什么是串? 下面让我们来了解一下串。 虽然看到串的第一眼,大家可能有一点蒙的感觉,串?羊肉串?或者是别的balabala的东西。其实这里的串,指的是字符串。 由D.E.Knuth,J.H.Morris和V.R.Pratt发表的一个模式匹配算法,简称KMP算法KMP模式匹配算法 在最开始,我们先来看一个串,s=abcababcaaccda……,t=abcabz,他们在进行匹配的时候,匹配到第六位时发现不匹配,按照朴素匹配算法,他们会依次往前移动一位,再重新进行比较 KMP的再改良 虽然介绍完了KMP算法的标准形式,但是,我发现在实际的操作中,有一些方面并不是很好操作,比如t[0],s[0]为字符串的长度,这里就需要进行一些别的操作实现,s[0],t[0]为字符串长度

    46221

    字符串匹配(一) -- 朴素匹配KMP 算法

    引言 软件算法中,最基础的算法要数排序和查找了,而字符串模式匹配算法可谓是基础中的基础,而最有名又最具代表性的字符串匹配算法要数 KMP 算法了,本文我们就来详细介绍一下 KMP 算法 2. KMP 算法 如果模式串为 ABCDE,我们通过上述的朴素字符串匹配算法与原字符串 ABCDFABCDE 进行匹配,假设经比较原字符串开始处的 ABCD 已经与模式匹配,而 E 却不匹配,按照朴素匹配算法 上述思想正是 KMP 算法的主要思想,只要理解了上述过程 KMP 算法就已经呼之欲出了。 3.1. ,针对 abab 这个模式字符串求解他的 next 数组为 [-1, 0, 0, 1] 当我们使用这个模式字符串匹配字符串 abacababc。 整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功。

    15020

    串的模式匹配算法KMP算法

    子串的定位操作通常称做串的模式匹配,是各种串处理系统中最重要的操作之一。 那我们完全可以不同时回溯指针i和j,直接将模式串往后移动3个单位进行匹配 利用这种“部分匹配”的特性,我们可以在遇到不匹配的时候,不将指针i回溯,而是尽量将模式串往右“滑动”特定单位长度进行继续匹配KMP算法算法由D.E.Knuth和V.R.Pratt和J.H.Morris同时发现的,人们称之为克努特-莫斯里-普拉特操作,简称KMP算法。 该算法能将时间复杂度降到O(n+m) 该算法关键在于求解next[],若令next[i]=j,则表示模式串中第i个字符与主串中相对应字符不匹配的时候,在模式串中需要重新和主串中该字符进行比较的字符的位置 j]) { next[i] = j + 1; } else { next[i] = 0; } } } int KMP

    8810

    串的模式匹配KMP算法

    串的模式匹配KMP算法 朴素模式匹配算法的问题 在之前我们介绍过串的朴素模式匹配算法,基本思路就是用主串中的每一个子串和模式匹配,若匹配失败,都是模式串后移一位再重新开始比较,将模式串序号j置为1 为了方便理解,这里举一个栗子,假设在主串a b a b c a b c a c b a b中匹配模式串a b c a c,朴素模式匹配算法的步骤如下 图片 从i=1,j=1开始匹配,当i=3,j=3 前缀:除了最后一个字符外,字符串的所有头部子串 后缀:除了第一个字符外,字符串的所有尾部子串 部分匹配值:字符串的前缀和后缀的最长相等前后缀长度 举个栗子:字符串a b a b a a的前缀和后缀都为 那我们这样想:如果已匹配相等的前缀序列中有某个后缀正好是模式串的前缀,那么我们就可以将模式串直接移动到这个后缀的位置。这就是KMP算法的主要思路。 那么如何来实现这个思路呢? [j] + 1 代码实现 KMP算法实现起来非常简短,以至于我第一次看见时觉得很不可思议,如此简短的代码就可以实现这么庞大的功能。

    7410

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • 高级威胁检测系统

      高级威胁检测系统

      腾讯云高级威胁检测系统(Network Traffic Analysis System,NTA)通过镜像方式采集企业网络边界流量,结合腾讯多年积累的海量安全数据,运用数据模型、安全模型、感知算法模型识别网络攻击及高级威胁(APT)。同时,对事件告警原始流量进行留存,方便事后追溯,可极大提升云环境下的威胁感知能力。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券