首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

目录 Brute-Force算法 Knuth-Morris-Pratt算法 确定有限状态自动机 部分匹配表 Boyer-Moore算法 Rabin-Karp算法 总结 ---- 网络信息中充满大量的字符串...对于非零状态,我们知道状态数会递增的条件是当且仅当发生匹配匹配连续,一旦有不连续情况发生,则必然产生状态退化。 这种动态的DFA需要一个叫部分匹配表的数组的支持。...理解了PMT后,算法步骤也就很清晰了: (1)寻找前缀后缀最长公共元素长度,构造PMT (2)根据PMT构造next数组 next数组考虑的是当前字符之前的字符串前后缀的相似度,所以通过步骤...Boyer-Moore算法 当可以在文本字符串中回退时,如果从右向左扫描模式字符串并将它和文本串匹配,那么就能得到一种非常快的字符串查找算法——Boyer-Moore算法。...总结 上述几种字符串匹配算法都各有特点,且在工业生产中都着应用。

2.9K20

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

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

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

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

    文章目录 BF算法 RK算法 编辑器中的全局替换方法:BM算法 坏字符 好后缀规则 代码实现 KMP算法 一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢?...有没有方法可以提高哈希算法计算子串哈希值的效率呢? 我们假设要匹配字符串的字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串的哈希值。...比如要处理的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。...我们事先计算好 26^0、26^1、26^2……26^(m-1),并且存储在一个长度为 m 的数组中 模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1),总共需要比较 n-m+1 个子串的哈希值...这是一个性能优于KMP的算法。 坏字符 BM 算法匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。 我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。

    2.2K20

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

    namespace std; #include //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>成功

    2.1K20

    【数据结构】数组字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

    关于字符串的基础知识亦可参考前文: 【重拾C语言】六、批量数据组织(三)数组初值;字符串、字符数组字符串数组;类型定义 typedef 【重拾C语言】七、指针(三)指针与字符串字符串字符串数组...具体C语言实现可参照前文: 【数据结构】数组字符串(十一):字符串的定义与存储(顺序存储、链式存储及其C语言实现) 4.3.2 字符串的基本操作 顺序存储:【数据结构】数组字符串(十二):顺序存储字符串的基本操作...(串长统计、查找、复制、插入、删除、串拼接) 链式存储:【数据结构】数组字符串(十三):链式字符串的基本操作(串长统计、查找、复制、插入、删除、串拼接) 4.3.3 模式匹配算法   文本编辑器中常用的...字符串匹配可以采用多种算法,包括朴素模式匹配算法、KMP(Knuth-Morris-Pratt)算法、Boyer-Moore算法等。...这种模式匹配算法被称为朴素的模式匹配算法, 2. ADL语言 3.

    15710

    字符串匹配算法详解

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

    1.5K30

    KMP字符串匹配算法

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

    1.5K10

    字符串匹配算法(BM)

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

    1.3K20

    算法 | KMP字符串匹配

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

    1.2K20

    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在模式串的位置,没有出现在模式串中。...字符串模式匹配算法的实现 (如果有两个位置匹配到了,返回第一个位置(位置从0开始算起)) #include #include using namespace...int len_fat = fat.length(); int len_sun = sun.length();  int fat_move[150] = {0}; //ASCII码一共128个字符,定义数组保存每次失配后主串应移动的距离...pos; //匹配后如果j等于字串的长度,则说明匹配成功 } } return -1; //父串结束后还是未匹配完成则说明子串不存在父串中,返回-1  } int main() { getline

    1.6K20

    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进制数。

    1.3K20

    字符串匹配:KMP算法

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

    2.5K100

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

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

    1.7K30

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

    1.8K30

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

    83610
    领券