在Boyer-Moore算法中，为什么“if (bmGs[j] == m)”是必要的？

在Boyer-Moore算法中，"if (bmGsj == m)"是必要的，因为它用于检查坏字符规则中的好后缀是否存在于模式字符串中。

Boyer-Moore算法是一种高效的字符串匹配算法，用于在文本中查找模式字符串的出现。它通过利用两个规则来跳过尽可能多的比较操作，从而提高匹配效率。这两个规则分别是坏字符规则和好后缀规则。

在坏字符规则中，当发现不匹配的字符时，算法会根据模式字符串中的字符在模式字符串中最后一次出现的位置，将模式字符串向右滑动一定的距离。这个距离由坏字符的位置决定。

而在好后缀规则中，当发现不匹配的字符时，算法会根据模式字符串中的好后缀的位置，将模式字符串向右滑动一定的距离。好后缀是指模式字符串中与文本中已匹配的后缀相匹配的子串。

在实现Boyer-Moore算法时，我们需要预先计算好后缀规则中的数组bmGs。这个数组存储了每个后缀在模式字符串中最右出现的位置。当发生不匹配时，我们根据bmGs数组中的值来确定滑动的距离。

在这个过程中，如果bmGsj等于m（模式字符串的长度），说明好后缀存在于模式字符串中，可以直接将模式字符串滑动到好后缀的位置。这样可以进一步减少比较操作，提高匹配效率。

总之，"if (bmGsj == m)"的判断是必要的，它用于检查好后缀是否存在于模式字符串中，以确定滑动的距离，从而提高Boyer-Moore算法的匹配效率。

腾讯云相关产品和产品介绍链接地址：

云计算产品：https://cloud.tencent.com/product
人工智能产品：https://cloud.tencent.com/product/ai
物联网产品：https://cloud.tencent.com/product/iotexplorer
移动开发产品：https://cloud.tencent.com/product/mobile
存储产品：https://cloud.tencent.com/product/cos
区块链产品：https://cloud.tencent.com/product/baas
元宇宙产品：https://cloud.tencent.com/product/metaspace

相关·内容

内存字符串暴力搜索定位代码

: Boyer-Moore字符匹配算法 Param: @text 要搜索的缓冲区开始 @n 要搜索的缓冲区大小 @pattern 需要匹配的字符串 @m 需要匹配的字符串长度 */ int BinarySearch...256; i++) {//一个字符占八位，共256个字符，把所有字符都覆盖到，这里的初始化是将所有字符失配时的移动距离都赋值为m bmBc[i] = m; } for (i = 0; i < m...- 1; i++) {//针对模式串pattern中存在的每一个字符，计算出它们最靠右的（非最后一个字符）地方距离串末尾的距离，即它们失配时该移动的距离,这一操作更新了初始化中一些字符的移动距离...字符匹配算法 Param: @text 文本内容 @n 文本内容长度 @pattern 需要匹配的字符串 @m 需要匹配的字符串长度 */ int BinarySearch(unsigned char...bmGs[i]); } } return -1; } 1.1 Boyer-Moore实现上面的代码是有注释,也是这个相同实现 void preBmBc(char *x, int m, int

5661 0

从入门到精通之Boyer-Moore字符串搜索算法详解

①由来介绍在用于查找子字符串的算法当中，BM（Boyer-Moore）算法是目前被认为最高效的字符串搜索算法，它由Bob Boyer和J Strother Moore设计于1977年。...是字符集大小，一般为256；搜索阶段时间复杂度是O(mn)；当模式串是非周期性的，在最坏的情况下算法需要进行3n次字符比较操作；算法在最好的情况下达到O(n / m)，比如在文本串bn中搜索模式串...（3）移动规则 BM算法的移动规则是：将3中算法基本框架中的j += BM()，换成j += MAX（shift（好后缀），shift（坏字符）），即 BM算法是每次向右移动模式串的距离是，按照好后缀算法和坏字符算法计算得到的最大值...图中v是text中的坏字符（对应位置i+j）,在pattern中对应不匹配的位置为i，那么pattern实际要右移的距离就是：bmBc[‘v’] – m + 1 + i。 ?...（2）计算好后缀数组bmGs[] 这里bmGs[]的下标是数字而不是字符了，表示字符在pattern中位置。如前所述，bmGs数组的计算分三种情况，与前一一对应。

1.5K8 0

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

进击算法：字符串匹配的 BM 算法 BM 算法介绍各种文本编辑器的 "查找" 功能（Ctrl+F），大多采用 Boyer-Moore 算法。 ?...Boyer-Moore 算法不仅效率高，而且构思巧妙，容易理解。1977 年，德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法。...总结下上面两种情况： u可以完整的再次出现在x中 u的后缀是x的前缀坏字符 ? 我们找到 y[i+j]=b 在x中最右出现的位置，如果没找到直接左对齐y[i+j+1]： ?...上面图中第一个说明是尾部不匹配的时候，我们查找字符a在pattern中的位置，假设是i，则Pattern shift的距离是 n-i 第二是是说如果失配发生在pattern中第j个位置，此时字符a在pattern...我们定义 l'(i) 是P[i..n]的最长后缀同时也是P[1..n]的前缀，如果不存在这样子的前缀，则l'[i] = 0，此时的含义是说，此时shift=n，为什么移动最大呢？

1.7K3 0

为什么在Jetson Orin上使用DLA是必要的？

关于DLA的基本知识：一篇文章回答你关于NVIDIA DLA的所有疑问 NVIDIA的DLA硬件是专门用于深度学习操作的固定功能加速器引擎。...NVIDIA的Jetson Orin SoC最多支持2个第二代DLA(第二代DLA在功耗效率方面表现最佳)，而Xavier SoC最多支持2个第一代DLA。...为什么在Orin上使用DLA是必要的？ DLA的峰值性能对Orin的总深度学习（DL）性能贡献在38%至74%之间（取决于电源模式，详见下表）。...DLA平均比GPU功耗效率高3倍至5倍（取决于电源模式和工作负载)，下表显示了在JetPack 5.1.1下，根据不同的电源模式，基于Jetson AGX Orin 64GB的DLA相对于GPU的性能与功耗比率...注意： Jetson AGX Orin 64GB在30W和50W功率模式下的DLA TOPs与用于汽车领域的DRIVE Orin平台的最大时钟频率相当。

8873 0

KMP、BM、Sunday等字符串匹配算法及实现

利用已经匹配的长度减去部分匹配值就可以得到模式串的移动位数。其实大白话就是现在主串匹配的子串在模式串中是否还存在，在计算NEXT值时则是利用已经匹配模式串的前缀和后缀，求前缀和后缀的最大长度。...表示在当前模式串到T[j]遇到失配的情况，在模式串中重新和主串匹配的位置 public static int[] get_Next(String str){ //对str求出各个字符位置的部分匹配值...//另一个则是依照好后缀规则得到的应该的移位数 //map中存放的是模式串中的各个字符，以及字符在模式串中倒叙的索引 private static void preBmBc(String pattern...中的length位置的字符是否在pattern中存在，如果存在，则返回，找不到 //则返回-1； int i=pattern.length()-1; while(i>=0&&pattern.charAt...，设置一个标识符有时候还是蛮必要的。

6342 0

为什么String在Java中是不可变的

String 在 Java 中是不可变的。不可变类只是一个无法修改其实例的类。创建实例时，将初始化实例中的所有信息，并且无法修改信息。不可变类有许多优点。...本文总结了为什么 String 设计为不可变的。这篇文章从内存，同步和数据结构的角度说明了不变性概念。 1. 字符串池字符串池（String intern pool）是方法区域中的特殊存储区域。...如果字符串是可变的，则使用一个引用更改字符串将导致其他引用的错误。 2. 缓存的哈希码字符串的哈希码经常在 Java 中使用。例如，在 HashMap 或 HashSet 中。...(new String("b")); set.add(new String("c")); for(String a: set) a.value = "a"; 在此示例中，如果 String 是可变的...字符串不是不可变的，连接或文件将被更改，这可能会导致严重的安全威胁。该方法认为它连接到一台机器，但事实并非如此。可变字符串也可能在 Reflection 中引起安全问题，因为参数是字符串。

1.3K2 0

字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？

至于选择哪一种字符串匹配算法，在不同的场景有不同的选择。在我们平时文档里的字符查找里 ? 采用的就是 Boyer-Moore 匹配算法了，简称BM算法。...接下来我们要在字符串中查找有没有和模式串匹配的字串，步骤如下：坏字符 1、 ? 和其他的匹配算法不同，BM 匹配算法，是从模式串的尾部开始匹配的，所以我们把字符串和模式串的尾部对齐。...（2）坏字符在模式串中的下标，在我们上面那个例子中，坏字符在模式串中的下标为 4，我们用变量 t2 来代表这个下标，如图 ?...我们把这些能够成功匹配的子串，称之为好后缀，所以呢，e，le，elp，mple 都是好后缀因为 e, le, elp在之前的步骤中，也是能够成功匹配。不过 mple 是最长的好后缀。...总结这篇文章我是采用直接举例子的方式来讲，我觉得这样反而容易懂，并且在讲的过程中，可能没有讲的那么全，这是因为我不想说的太全，因为把所有情况都罗列处理的话，相信你容易晕。

1.8K3 0

为什么边缘计算在数据驱动的世界中是创新的必要条件?

大量数据可能会定期从远程位置和全球任何地方的工作环境实时运行的传感器和物联网设备中获取，而人们如今已经淹没在信息的海洋中。边缘计算的过程是什么? 边缘计算完全取决于位置。...在传统的企业计算中，数据是在客户端创建的，其中包括用户的计算机。该数据通过广域网(WAN)(例如Web)发送到企业LAN，在那里由企业应用程序存储和处理，其处理的结果随后被发送回客户端。...隐私与安全从安全角度来看，边缘计算设施存储和处理的数据可能存在风险，尤其是当它由各种不如集中式或基于云计算的解决方案安全设备进行处理时。...许多运营商正在将边缘计算技术纳入其5G实施中，以提供更快的实时处理，特别是对于便携式设备、智能汽车和自动驾驶汽车，而不是简单地提供更高的速度并让企业继续在云端处理数据。...Verizon公司的目标是让边缘节点虚拟地驻留在客户附近，通过5G的网络切片功能划分出一些频谱，以实现即时、无需安装的连接。

4845 0

Python 中的字符串匹配算法

然而，Python 中的字符串匹配算法并不是一成不变的，它会根据不同的情况而使用不同的算法。因此，了解 Python 中的字符串匹配算法非常有必要。...KMP算法的基本思想是，在比较两个字符串时，利用已经匹配的子串的信息来减少比较的次数。KMP算法的优点是效率较高，时间复杂度为 O(m+n)，其中 m 和 n 分别是字符串的长度。...Boyer-Moore算法：Boyer-Moore算法是另一种改进的字符串匹配算法。Boyer-Moore算法的基本思想是，在比较两个字符串时，从字符串的末尾开始，逐个字符地比较两个字符串。...Boyer-Moore算法的优点是效率较高，时间复杂度为 O(m+n)，其中 m 和 n 分别是字符串的长度。...以下是一个使用Boyer-Moore算法在 Python 中实现的字符串匹配函数：def boyer_moore_string_matching(text, pattern): """ Boyer-Moore

220 0

通用高效字符串匹配--Sunday算法

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似, 其效率在匹配随机的字符串时不仅比其它匹配算法更快，而且 Sunday 算法的实现比 KMP、BM 的实现容易很多...只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。...因此想办法减少不必要的匹配，就能提高效率咯。很多高效的字符串匹配算法，它们的核心思想都是一样样的，想办法利用部分匹配的信息，减少不必要的尝试。...Sunday算法利用的是发生失配时查找串中的下一个位置的字母。还是用图来说明： ?...Sunday算法实际上是对Boyer-Moore算法的优化，并且它更简单易实现。其论文中提出了三种不同的算法策略，结果都优于Boyer-Moore算法。 Reference: 1] [D.M.

1.4K2 0

如何用Java实现字符串匹配和替换的高效算法？

Brute Force（暴力法）：这是最简单的字符串匹配算法，也是最低效的。它的思想是逐个比较目标字符串中的字符与要匹配的子字符串字符是否相等。...时间复杂度为O(mn)，其中m是目标字符串长度，n是子字符串长度。...KMP算法： KMP（Knuth-Morris-Pratt）算法通过利用已经匹配过的信息来减少不必要的字符比较次数，进而提高效率。时间复杂度为O(m+n)。...Boyer-Moore算法： Boyer-Moore算法通过预处理模式串，跳过尽可能多的字符，从而实现快速的字符串匹配。时间复杂度为O(mn)。...无论是字符串匹配还是替换，选择合适的算法和方法取决于具体的需求。在实际应用中，可以根据字符串的长度和匹配/替换的频率来评估不同算法的性能，从而选择最合适的算法。

2411 0

Python数据结构与算法-在M个数中找K个最小的数

题目：输入M个数，从中找到K个最小的数比如输入10,-9,0,100,90,1,4,-9；找到最小的3个数为：-9，-9，0 1这道题最坏的办法是对M个数进行排序，排序算法最好的时间复杂度是o(mlogm...) 2 第二种办法，是对其中的K个数进行排序，时间复杂度是o(m*k*logk),这要对比m和k*logk的大小，看哪个办法更优 3 对于第二种方法的一个优化是，不需要对K个数进行排序，只需要要到这K个数中最大的数...A，然后下一个数跟A对比，比A大则不要，比A小则入选，如此循环；时间复杂度是o(m*k) 4 最后一种是对方法3的一个优化，在找数组K个数中最大数时，最好的时间复杂度是用大根堆的方式，时间复杂度是logk...,整体的时间复杂度是o(m*logk)。...这样最后堆里的内容就是要输出的内容下面是第四种方式的代码： ''' 查找最小的k个元素题目：输入n个整数，输出其中最小的k个。

1.4K1 0

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

大家好，又见面了，我是你们的朋友全栈君。文章目录 1. BM（Boyer-Moore）算法 1.1 坏字符规则 1.2 好后缀规则 1.3 两种规则如何选择 2....BM（Boyer-Moore）算法思想：有模式串中不存在的字符，那么肯定不匹配，往后多移动几位，提高效率 BM原理：坏字符规则，好后缀规则 1.1 坏字符规则利用坏字符规则，BM算法在最好情况下的时间复杂度非常低...BM算法代码实现 2.1 坏字符找到坏字符在模式串中的位置(有重复的，则是靠后的那个) 采用哈希，而不是遍历。...”证明了在最坏情况下，BM算法的比较次数上限是5n。...---- BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。

1.8K2 0

子字符串查找----Boyer-Moore算法（从右向左匹配）

Boyer-Moore算法是一种从右向左扫描模式字符串并将它与文本匹配的算法。举例说明Boyer-Moore算法：有文本FINDINAHAYSTACKNEEDLE和模式字符串NEEDLE....因为是从右向左扫描，所以会先比较模式中最后一位E和文本中下标为5的N。不匹配，因为模式字符串中也出现了N，则右移模式字符串使得模式中最右边的N（这里是位置0的N）与文本中的相应N对齐。...要实现之，需要一个数组right[]保存字母表中每个字母在模式字符串中出现的最靠右的下标（如果不存在则为-1）。这个值揭示了如果发生不匹配，应该右跳跃多远。...在right[]数组计算后，算法实现起来就非常容易了。用一个索引i在文本中从左向右移动，用索引j在模式字符串中从右向左移动。...内循环检查检查正文和模式字符串在位置i是否相等，如果从M-1到0的所有j，txt.charAt(i+j)都和pat.charAt(j)相等，就是找到了匹配。

1.2K0 0

字符串——28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。...说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。...，因此可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt算法、Boyer-Moore算法、Sunday 算法等，本文将讲解Knuth-Morris-Pratt...为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回—1。...复杂度分析时间复杂度:o(n x m)，其中n是字符串hagystack的长度，m是字符串needle的长度。

3053 0

为什么在深度学习中，AlphaGo Zero是一个巨大的飞跃?

AlphaGo Zero是DeepMind的自动操作系统的最新化身。有人可能会认为，在围棋中击败人类世界冠军是很难的。...然而，在这里，每一个训练集都是全新的，而且越来越具有挑战性。它也类似于课程学习，然而课程是在算法中固有的。训练集是自生成的，目标函数的计算是由蒙特卡罗树搜索(MCTS)的结果推导而来的。...AlphaGo所展示的东西是闻所未闻的，也就是说，它需要的资源少得多，设计也不那么复杂，同时还能明确地击败所有以前的算法。...在这两种情况下，你都有两个在训练中互相馈送的网络。每个人都应该想到的一个重要问题是:“AlphaGo Zero的算法有多普遍?”DeepMind曾公开表示，他们将把这项技术应用于药物研发领域。...它可以有效地做到这一点，因为所有其他的不确定因素都是已知的。也就是说，在一系列行为的结果中没有不确定性，行为效果是可以预测的。简而言之，博弈的行为是可以预测的。

9378 0

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

在查找中，dfa[str[i][j]是在比较了str[i]和pat[j]之后应该和str[i+1]比较的模式字符的位置。在匹配成功时会继续比较下一个字符，因此dfa[pat[j]][j]总是j+1。...因为在计算DFA的第j个状态时只需要知道DFA是如何处理前j-1个字符的，所以总能从尚不完整的DFA中得到所需的信息。...Boyer-Moore算法当可以在文本字符串中回退时，如果从右向左扫描模式字符串并将它和文本串匹配，那么就能得到一种非常快的字符串查找算法——Boyer-Moore算法。...虽然在最坏情况下RK算法的运行时间仍然是O(NM)，但在实际使用过程中，Rabin-Karp的复杂度通常被认为是O(N+M)。...，能够保证最坏情况下也是线性级别的性能，且不需要回退文本串指针；Boyer-Moore算法的性能在一般情况下都是亚线性级别（可能是线性级别的M倍），且对于越长的模式串其速度可能会越快；Rabin-Karp

2.9K2 0

字符串匹配算法（BM）

BM（Boyer-Moore）算法思想：有模式串中不存在的字符，那么肯定不匹配，往后多移动几位，提高效率 ? BM原理：坏字符规则，好后缀规则 1.1 坏字符规则 ?...利用坏字符规则，BM算法在最好情况下的时间复杂度非常低，是O（n/m）。比如，主串是aaabaaabaaabaaab，模式串是aaaa。...BM算法代码实现 2.1 坏字符找到坏字符在模式串中的位置(有重复的，则是靠后的那个) 采用哈希，而不是遍历。 ?..."证明了在最坏情况下，BM算法的比较次数上限是5n。...---- BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。

1.3K2 0

SpringBoot+Neo4j在社交电商中，讲述你是怎么被绑定为下线的

上两篇文章我们主要讲解了Neo4j的基本知识以及Neo4j的基本使用，这篇文章我们就以实例来深入的理解一下，我们以社交电商中的绑定关系为例，使用SpringBoot+Neo4j来实现。...Neo4j文章回顾：不懂Neo4j？没关系，一起学图文并茂教你学会操作图数据库Neo4j 一、分析社交电商中，现在做的比较出色的就应该属于花生日记，以及最近比较火的芬香。...3.添加Neo4j 节点类这里添加一个MemberInvit节点，有点注解类似于Mysql中的table 映射的对象类，mysql中叫做ORM，neo4j中叫做OGM。...这里要使用到的是 @NodeEntity 注解和 @Id注解。 @NodeEntity声明该类为Neo4j的节点类 @Id Neo4j的主键。...增加完后，我们有两种方法查看，一是在Neo4j的控制台查看，另一个是在代码中查看。这里我们先在Neo4j的控制台查询下： ? 说明官方用户已经增加成功了。

6941 0

为什么说监控软件中应用弗洛伊德算法是更加有效的

弗洛伊德算法（Floyd算法）是一种用于寻找加权图中最短路径的算法。在监控软件中，可以使用弗洛伊德算法来帮助优化路线规划或者监控摄像头的布局。...然后，使用弗洛伊德算法来计算每个小区域之间的最短路径，并将这些路径用于确定最佳的摄像头布局方案。弗洛伊德算法在监控软件中的一个例子是通过使用该算法来帮助优化监控摄像头的布局和路径规划。...例如，在大型建筑物内布置监控摄像头，可以使用弗洛伊德算法来确定最佳的摄像头布局方案。...该算法可以计算出从一个小区域到另一个小区域的最短路径，并将这些路径用于确定最佳的摄像头摆放位置，从而提高监控系统的效率和可靠性。弗洛伊德算法的优势之一是可以解决多源点、多汇点的最短路径问题。...因此，在实际应用中，需要根据具体的场景和需求，综合考虑算法的优缺点，选择适合的算法或者采取合适的优化措施来提高计算效率和准确性。

3153 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云