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

字符串匹配算法_字符串模式匹配算法

,对信息搜寻至关重要,因此子字符串查找(即字符串匹配)是使用频率非常高操作:给定一段长度为N文本和长度为M模式字符串(N≥M),在文本中找到一个和模式串相匹配子串。 确定有限状态自动机 KMP算法寻找匹配字符串核心过程可以用确定有限状态自动机(Deterministic Finite Automation,DFA),对于每一个状态转换都有一定转换条件,在字符串匹配中 Boyer-Moore算法 当可以在文本字符串中回退时,如果从右向左扫描模式字符串并将它和文本串匹配,那么就能得到一种非常快字符串查找算法——Boyer-Moore算法。 它效率来自于这样事实:对于每一次失败匹配尝试,算法都能够使用这些信息来排除尽可能多无法匹配位置。即它充分利用待搜索字符串一些特征,加快了搜索步骤。 简明算法思想使得即使在对于需要在输入流中匹配字符串时,构造缓冲机制也是可接受选择。 实际上,BM算法还可以更快,可以移动更大距离。

30620

字符串匹配算法_多字符串匹配

文章目录 BF算法 RK算法 编辑器中全局替换方法:BM算法 坏字符 好后缀规则 代码实现 KMP算法 一说到字符串匹配算法,不知道会有多少小伙伴不由自主想起那个kmp算法呢? 想到是很正常,谁让它那么优秀呢。 ---- BF算法 不要被事物表面现象所迷惑,这个算法全称:Brute Force,有个拉风中文名:暴力匹配算法。 能想明白了吧。 我们假设要匹配字符串字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串哈希值。 比如要处理字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。 比方说要在我这篇博客里找出全部“主串”这个词,有没有想过其底层原理? 这是一个性能优于KMP算法。 坏字符 BM 算法匹配顺序比较特别,它是按照模式串下标从大到小顺序,倒着匹配

13420
  • 广告
    关闭

    新年·上云精选

    热卖云产品新年特惠,2核2G轻量应用服务器9元/月起,更多上云必备产品助力您轻松上云

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

    字符串匹配---BF算法--朴素模式匹配算法

    int sizeA=a.length();//返回字符串中字符个数 //求出b串长度 int sizeB = b.length(); //i指向A,j指向B子串 int i=0; int //当前j值等于i移动次数,i现在值减去i移动次数,回到i起始位置 //往后移动一次,相当于加1 i = i - j + 1; //j回到子串头部 j = 0; } } //i值是按下标从0开始本身应该是8,j值本身应该是4,但最后一次匹配成功后,还有一次i++和j++ cout << "循环结束后i=" << i << endl; cout << "循环结束后j=" << j << endl; //判断是<em>匹配</em>成功还是<em>匹配</em>失败 if (j == sizeB) { //退出循环时i记录<em>的</em>是自串<em>的</em>最后一个字符在主串中<em>的</em>位置加一 //j 记录<em>的</em>是子串<em>的</em>最后一个元素<em>的</em>位置加一,等于子串<em>的</em>长度 //i-j得到<em>的</em>是子串<em>的</em>第一个字符在主串中<em>的</em>位置 return i-j;//<em>匹配</em>成功,返回子串在主串中<em>的</em>起始位置 } else {

    38620

    字符串匹配算法_多字符串匹配

    BM(Boyer-Moore)算法 思想:有模式串中不存在字符,那么肯定不匹配,往后多移动几位,提高效率 BM原理:坏字符规则,好后缀规则 1.1 坏字符规则 利用坏字符规则,BM算法最好情况下时间复杂度非常低 每次比对,模式串都可以直接后移四位,所以,匹配具有类似特点模式串和主串时候,BM算法非常高效。 单纯使用坏字符规则还是不够。 总结 BM算法内存消耗 整个算法用到了额外3个数组,其中bc数组大小跟字符集大小有关,suffix数组和prefix数组大小跟模式串长度m有关。 如果处理字符集很大字符串匹配问题,badchar数组对内存消耗就会比较多。 ---- BM算法核心思想是,利用模式串本身特点,在模式串中某个字符与主串不能匹配时候,将模式串往后多滑动几位,以此来减少不必要字符比较,提高匹配效率。

    14120

    字符串匹配KMP算法

    关于字符串匹配KMP算法其实不难,只要理解字符串下一步匹配需要移动个数就可以了,但是说是这么说,实际理解肯定会有或多或少问题,要是大家看完之后还是有问题有疑问同学,可以再文章底部加我~ 字符串匹配 KMP算法 字符串匹配是计算机基本任务之一。 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer文章,我才真正理解这种算法。下面,我用自己语言,试图写一篇比较好懂KMP算法解释。 1. ? 因为B与A不匹配,搜索词再往后移。 3. ? 就这样,直到字符串有一个字符,与搜索词第一个字符相同为止。 4. ? 接着比较字符串和搜索词下一个字符,还是相同。 5. ? "部分匹配"实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它"部分匹配值"就是2("AB"长度)。

    71540

    进击算法字符串匹配 BM 算法

    进击算法字符串匹配 BM 算法 BM 算法介绍 各种文本编辑器 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。 ? Boyer-Moore 算法不仅效率高,而且构思巧妙,容易理解。1977 年,德克萨斯大学 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法。 好后缀 假设匹配过程中发现x[i]=a 和 y[i+j] = b 不同,此时当前匹配信息有: x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u x[i] ! 上面图中第一个说明是尾部不匹配时候,我们查找字符a在pattern中位置,假设是i,则Pattern shift距离是 n-i 第二是是说如果失配发生在pattern中第j个位置,此时字符a在pattern 因为我们先去找Patten中是否存在P[i..n],因为如果要匹配,则pattern中必须要存在P[1..L'(i)],但是不幸是没找到,这个时候我们可以直接先shift i-1,然后在慢慢右移,直到

    87730

    字符串匹配KMP算法

    字符串匹配是计算机基本任务之一。 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? ? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用之一。它以三个发明者命名,起头那个K就是著名科学家Donald Knuth。 ? 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer文章,我才真正理解这种算法。下面,我用自己语言,试图写一篇比较好懂KMP算法解释。 1. ? 因为B与A不匹配,搜索词再往后移。 3. ? 就这样,直到字符串有一个字符,与搜索词第一个字符相同为止。 4. ? 接着比较字符串和搜索词下一个字符,还是相同。 5. ? "部分匹配"实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它"部分匹配值"就是2("AB"长度)。

    66660

    字符串匹配算法详解

    菜馆内的人都松了一口气 通过上面的一个例子,让我们简单了解了字符串匹配,下面我们一起来详细了解一下吧。 字符串匹配:设 S 和 T 是给定两个串,在主串 S 中找到模式串 T 过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现位置,否则匹配不成功, 解决上面问题算法我们称之为字符串匹配算法,今天我们来介绍三种字符串匹配算法,大家记得打卡呀,说不准面试时候就问到啦。 实现 strStr() 题目描述 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现第一个位置 (从0开始)。 如上图所示,如果我们利用 BF 算法,遇到不匹配字符时,每次右移一位模式串,再重新从头进行匹配,我们观察一下,我们模式串 abcdex 中每个字符都不一样,但是我们第一次进行字符串匹配时,abcde

    31630

    字符串匹配:KMP算法

    KMP算法是一种改进字符串匹配算法,由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特—莫里斯—普拉特算法。 KMP算法主要分为两个步骤:字符串自我匹配,目标串和模式串之间匹配。 ? KMP.jpg (一)字符串自我匹配 所谓字符串自我匹配,就是看字符串中左右侧相等最长子串字符个数。 下面用几个具体例子来说明: 例1:字符串1212121 从最左边开始算起,1没有子串,匹配字符个数为0; 12左右两侧没有相等子串,匹配字符个数为0; 121左右侧有相同子串1,匹配字符个数为 综上所述,字符串aaaa自我匹配结果为0,1,2,3 例3:字符串abaabab 从最左边开始算起,a没有子串,匹配字符个数为0; ab左右侧没有相同子串,匹配字符个数为0; aba 综上所述,字符串abaabac自我匹配结果为0,0,1,1,2,3,2 从上面的3个例子中,咱们看看能否找到什么规律,这个规律可以使得咱们在字符串自我匹配过程中不需要每次都从第一个字符开始比较呢?

    1.3K100

    iOS算法——字符串匹配

    字符串匹配问题: 给你⼀个仅包含⼩写字⺟字符串主串S = "abcacabdc",模式串T = "abd", 请查找出模式串在主串第 ⼀次出现位置; 提示: 主串和模式串均为⼩写字⺟且都是合法输⼊。 方案一:BF算法 何为BF算法: BF算法即暴风算法,是普通模式匹配算法。 BF算法思想:将目标串S第一个字符与模式串T第一个字符进行匹配,若相等,则继续比较S第二个字符和 T第二个字符;若不相等,则比较S第二个字符和T第一个字符,依次比较下去,直到得出最后匹配结果 从主串下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较; 如果j > T.length, 说明模式T中每个字符串依次和主串S找中一个连续字符序列相等,则匹配成功 RK算法求解过程: 将我们用来比较字符串全集设为∑={a,b,…,z},设∑长度为d=|∑|,则主串和模式串都可以看作是d进制数。

    21220

    KMP 字符串匹配算法

    KMP(Knuth-Morris-Pratt) 算法是一种常见字符串匹配算法,在主字符串 S 中查找字符串 M 出现起始位置,通过 M 自身信息来减少无效查询次数。 ,从 S 第一个字符开始 len(M) 个字符串与 M 进行匹配,如果匹配成功则返回位置,如果不成功则从 S 第二个字符开始 len(M) 个字符串与 M 进行匹配,循环向后进行匹配判断,直到剩余字符串长度小于 KMP算法 在了解KMP算法之前,首先看两个貌似无关概念:前缀和后缀。前缀是指除最后一个字符或多个字符字符串组合,后缀是指除第一个字符或多个字符字符串组合。 KMP算法中查找 M 在 S 中位置,在匹配过程中,通过分析 M 与 S 匹配字符串信息来避免回退现象,过程如下: 从 S 第一个字符开始进行逐个扫描对比: ? 此时匹配长度 n 为 7, i 指向值 F 和 j 指向值 E 不同 此时已匹配字符串为 T:ABDCABD,长度为 7,由之前概念可知,该字符串部分匹配长度为 3,即字符串 PM:ABD

    72330

    字符串匹配算法(BM)

    BM(Boyer-Moore)算法 思想:有模式串中不存在字符,那么肯定不匹配,往后多移动几位,提高效率 ? BM原理:坏字符规则,好后缀规则 1.1 坏字符规则 ? 利用坏字符规则,BM算法最好情况下时间复杂度非常低,是O(n/m)。比如,主串是aaabaaabaaabaaab,模式串是aaaa。 每次比对,模式串都可以直接后移四位,所以,匹配具有类似特点模式串和主串时候,BM算法非常高效。 单纯使用坏字符规则还是不够。 如果处理字符集很大字符串匹配问题,badchar数组对内存消耗就会比较多。 ---- BM算法核心思想是,利用模式串本身特点,在模式串中某个字符与主串不能匹配时候,将模式串往后多滑动几位,以此来减少不必要字符比较,提高匹配效率。

    48320

    KMP字符串匹配算法

    KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人提出一种快速模式匹配算法 KMP朴素算法 原理:子串pattern依次与目标串target中字符比较,如果相等,继续比较下一个字符;如果不等,pattern右移一位,重新开始比较,直至匹配正确或超出target。 如果P右移1位,P前两字符aa又将与T(target)ab不匹配 如果P右移2位,P第一个字符a就与Tb不匹配 如果P右移3位,P前两字符aa又将于Tab不匹配(同右移1位情况) 如果P右移4位 KMP算法 KMP算法,是由KMP朴素算法演变而来,主要分为两步: 第一步,当字符串比较出现不等时,确定下一趟比较前,应该将子串pattern右移多少个字符(预处理) 第二步,子串pattern右移后 总结: 第一步,其实就是KMP朴素算法对模式匹配子串pattern预处理过程,上面已经给出了算法公式和代码示例 第二步,本质上就是KMP朴素算法,不同仅仅是pattern右移位数大小由其预处理过程决定

    67810

    Sunday 字符串匹配算法

    /*Sunday算法是比较快匹配算法(据说比KM还快), 算法主要思想是当父串和字串不匹配时,父串移动尽可能多字符,提高匹配效率。 比如: 匹配串:O U R S T R O N G X S E A R C H 模式串:S E A R C H 这里我们看到O-S不相同,我们就看匹配串中O在模式串位置,没有出现在模式串中。 匹配串:O U R S T R O N G X S E A R C H 模式串: _ _ _ _ _ _ _ _ S E A R C H 移动模式串,使模式串首字符和O下一个字符对齐。 字符串模式匹配算法实现 (如果有两个位置匹配到了,返回第一个位置(位置从0开始算起)) #include <iostream> #include <string> using namespace pos; //匹配后如果j等于字串长度,则说明匹配成功 } } return -1; //父串结束后还是未匹配完成则说明子串不存在父串中,返回-1  } int main() { getline

    87920

    算法 | KMP字符串匹配

    字符串是不可变数据类型,也就是说你要改变原字符串元素,只能是新建另一个字符串字符串匹配就是基于最简单字符比较,其中模式串就是普通字符串,所做匹配是在目标串里查找等于模式串子串。 也就是说,比较一方是表示模式字符串,另一方是目标字符串所有可能子串。我们常用就是朴素匹配算法和无回溯串匹配算法(KMP算法)。 2. (1) 朴素匹配算法 最简单朴素匹配算法采用最直观可行策略: (1)从左到右逐个字符匹配;(2)发现不匹配时,转去考虑目标串里下一个位置是否与模式串匹配。 (KMP算法) 在状态(0)匹配到第一个c失败时,由于已知前两个字符不同,KMP算法直接把模式串移两个位置,模式串开头a移到c匹配失败位置,达到状态(1)。 结语 字符串匹配处理关键就是字符处理后栈是否为空。当所有字符处理完成后,栈为空则字符串匹配成功。反之若栈不为空,则表示字符串匹配失败。 where2go 团队 ----

    45020

    算法字符串匹配(查找)-BF算法

    欢迎点击「算法与编程之美」↑关注我们! 本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。 字符串是数据结构中比较简单一种,但又是我们最常用数据结构之一。 对于字符串对象,最重要操作之一便是字符串匹配(查找),本篇文章便向大家介绍一个典型匹配算法—BF算法 为了方便理解,我们直接从问题入手,来理解这两种算法。 BF算法 目标串:BBC ABCDAB ABCD ABCDABDE 模式串:ABCDABD 提示:(空格也是一个字符串) 问题:查看模式串是否出现在目标串中,并找出其在目标串中下标位置 分析:大家在碰到这个问题时 输出字符串匹配失败 注意: 很多人在自己思考这个问题时,会犯一个错误。 更多精彩文章: 算法|从阶乘计算看递归算法 算法|字符串匹配(查找)-KMP算法 JavaScript|脚本岂能随意放置 Web|设置隔行变色单元格 开发|优秀Java工程师“对象”一定不错

    61830

    字符串匹配算法(KMP)

    KMP由来 上一节说BM算法是最高效、最常用字符串匹配算法。 最知名却是KMP,它3位作者(D.E.Knuth,J.H.Morris,V.R.Pratt),算法全称是Knuth Morris Pratt 算法,简称KMP算法。 2. KMP算法基本原理 类似于BM里概念:坏字符(不能匹配),好前缀(已经匹配那段) ? ? KMP算法目的:当遇到坏字符后,对于已经对比过好前缀,将模式串多滑动几位 ? = b[j] , 则我要在前面部分里寻找能和包含 b[j] 后缀匹配最长前缀子串; b[k] 前面的最长匹配前缀长度就是 next[k],那么其后面一个字符就是 b[ next[k] ],如果它等于 代码 王争代码不好理解,找了书和别的人代码参考 /** * @description: KMP字符串匹配算法 * @author: michael ming * @date: 2019/6/22

    19610

    关注

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

    相关产品

    • 腾讯知识图谱

      腾讯知识图谱

      腾讯知识图谱是一个集成图数据库、图计算引擎和图可视化分析的一站式平台。支持抽取和融合异构数据,支持千亿级节点关系的存储和计算,支持规则匹配、机器学习、图嵌入等图数据挖掘算法,拥有丰富的图数据渲染和展现的可视化方案……

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券