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

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

目录 Brute-Force算法 Knuth-Morris-Pratt算法 确定有限状态自动机 部分匹配表 Boyer-Moore算法 Rabin-Karp算法 总结 ---- 网络信息中充满大量的字符串 确定有限状态自动机 KMP算法寻找匹配字符串的核心过程可以用确定有限状态自动机(Deterministic Finite Automation,DFA),对于每一个状态的转换都有一定的转换条件,在字符串匹配中 Boyer-Moore算法 当可以在文本字符串中回退时,如果从右向左扫描模式字符串并将它和文本串匹配,那么就能得到一种非常字符串查找算法——Boyer-Moore算法。 事实上,BM(Boyer-Moore)算法是目前被认为最高效的字符串搜索算法, 一般情况下,比KMP算法3-5倍,它由Bob Boyer和J Strother Moore设计于1977年。 总结 上述几种字符串匹配算法都各有特点,且在工业生产中都着应用。

29920

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

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

13620
  • 广告
    关闭

    新年·上云精选

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

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

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

    文章目录 BF算法 RK算法 编辑器中的全局替换方法:BM算法 坏字符 好后缀规则 代码实现 KMP算法 一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢? 有没有方法可以提高哈希算法计算子串哈希值的效率呢? 我们假设要匹配字符串的字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串的哈希值。 比如要处理的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。 所以,RK 算法整体的时间复杂度就是 O(n)。 但是呢,还有一个很致命的问题,叫做数值过大。 以幂增的速度是非常的,用不了多久int就hold不住了啊,那要怎么办? 这是一个性能优于KMP的算法。 坏字符 BM 算法匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。 我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。

    13020

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

    namespace std; #include<string> //BF int BF(string& a,string& b) { //求出a串的长度 int sizeA=a.length();//返回的是字符串中字符个数 //往后移动一次,相当于加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 ( 退出循环时i记录的是自串的最后一个字符在主串中的位置加一 //j记录的是子串的最后一个元素的位置加一,等于子串的长度 //i-j得到的是子串的第一个字符在主串中的位置 return i-j;//<em>匹配</em>成功

    37720

    字符串匹配算法详解

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

    31430

    字符串匹配: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进制数。

    20320

    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 中位置不需要进行回退,可以减少无效的回退造成的性能浪费。

    71830

    字符串匹配算法(BM)

    BM(Boyer-Moore)算法 思想:有模式串中不存在的字符,那么肯定不匹配,往后多移动几位,提高效率 ? BM原理:坏字符规则,好后缀规则 1.1 坏字符规则 ? 每次比对,模式串都可以直接后移四位,所以,匹配具有类似特点的模式串和主串的时候,BM算法非常高效。 单纯使用坏字符规则还是不够的。 所以,BM算法还需要用到“好后缀规则”。 1.2 好后缀规则 ? 从好后缀的后缀子串中,找一个最长的且和模式串的前缀子串匹配的 {v},滑动至 {v} 对齐 ? 如果处理字符集很大的字符串匹配问题,badchar数组对内存的消耗就会比较多。 ---- BM算法核心思想是,利用模式串本身的特点,在模式串中某个字符与主串不能匹配的时候,将模式串往后多滑动几位,以此来减少不必要的字符比较,提高匹配的效率。

    48020

    KMP字符串匹配算法

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

    67310

    算法 | KMP字符串匹配

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

    44720

    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

    87720

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

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

    61230

    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。

    17440

    字符串匹配算法(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

    19110

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

    引言 软件算法中,最基础的算法要数排序和查找了,而字符串模式匹配算法可谓是基础中的基础,而最有名又最具代表性的字符串匹配算法要数 KMP 算法了,本文我们就来详细介绍一下 KMP 算法 2. 朴素匹配算法 最简单的算法就是朴素匹配算法了,所谓的“朴素匹配算法”指的就是人们常说的“暴力匹配算法”。 KMP 算法 如果模式串为 ABCDE,我们通过上述的朴素字符串匹配算法与原字符串 ABCDFABCDE 进行匹配,假设经比较原字符串开始处的 ABCD 已经与模式串匹配,而 E 却不匹配,按照朴素匹配算法 是因为已匹配部分的字符串没有重复字符,如果已匹配字符串拥有重复字符,情况又会变得不一样。 ,针对 abab 这个模式字符串求解他的 next 数组为 [-1, 0, 0, 1] 当我们使用这个模式字符串匹配字符串 abacababc。

    15120

    关注

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

    相关产品

    • 智能审核

      智能审核

      腾讯云视频AI智能审核借助 AI 对视频内容(CV、ASR、OCR)进行涉黄、涉政、涉暴、违规检测,支持自定义审核模版,支持大客户审核测试集定制,检测范围准包含色情、性感、亲密行为、敏感台标、敏感人物库(落马官员等)、敏感网站、暴力血腥、武器等多维度。支持截帧间隔可配,并支持多种音视频格式以及编码算法。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券