【yabo亚搏手机最新版app】云漫圈 | 什么是字符串匹配算法?

作者:yabo亚搏手机最新版app发布时间:2022-02-04 12:53

本文摘要:作者 | 法式员小灰泉源 | 法式员小灰(ID:chengxuyuanxiaohui )————— 第二天 —————什么意思呢?让我们来举一个例子:在上图中,字符串B是A的子串,B第一次在A中泛起的位置下标是2(字符串的首位下标是0),所以返回 2。我们再看另一个例子:在上图中,字符串B在A中并不存在,所以返回 -1。为了统一观点,在后文中,我们把字符串A称为主串,把字符串B称为模式串。

yabo亚搏手机最新版app

作者 | 法式员小灰泉源 | 法式员小灰(ID:chengxuyuanxiaohui )————— 第二天 —————什么意思呢?让我们来举一个例子:在上图中,字符串B是A的子串,B第一次在A中泛起的位置下标是2(字符串的首位下标是0),所以返回 2。我们再看另一个例子:在上图中,字符串B在A中并不存在,所以返回 -1。为了统一观点,在后文中,我们把字符串A称为主串,把字符串B称为模式串。

小灰的想法简朴粗暴,让我们用下面的例子来演示一下:第一轮,我们从主串的首位开始,把主串和模式串的字符逐个比力:显然,主串的首位字符是a,模式串的首位字符是b,两者并不匹配。第二轮,我们把模式串后移一位,从主串的第二位开始,把主串和模式串的字符逐个比力:主串的第二位字符是b,模式串的第二位字符也是b,两者匹配,继续比力:主串的第三位字符是b,模式串的第三位字符也是c,两者并不匹配。

第三轮,我们把模式串再次后移一位,从主串的第三位开始,把主串和模式串的字符逐个比力:主串的第三位字符是b,模式串的第三位字符也是b,两者匹配,继续比力:主串的第四位字符是c,模式串的第四位字符也是c,两者匹配,继续比力:主串的第五位字符是e,模式串的第五位字符也是e,两者匹配,比力完成!由此获得效果,模式串 bce 是主串 abbcefgh 的子串,在主串第一次泛起的位置下标是 2:以上就是小灰想出的解决方案,这个算法有一个名字,叫做BF算法,是Brute Force(暴力算法)的缩写。上图的情况,在每一轮举行字符匹配时,模式串的前三个字符a都和主串中的字符相匹配,一直检查到模式串最后一个字符b,才发现不匹配:这样一来,两个字符串在每一轮都需要白白比力4次,显然很是浪费。

假设主串的长度是m,模式串的长度是n,那么在这种极端情况下,BF算法的最坏时间庞大度是O(mn)。————————————比力哈希值是什么意思呢?用过哈希表的朋侪们都知道,每一个字符串都可以通过某种哈希算法,转换成一个整型数,这个整型数就是hashcode:hashcode = hash(string)显然,相对于逐个字符比力两个字符串,仅比力两个字符串的hashcode要容易得多。

给定主串和模式串如下(假定字符串只包罗26个小写字母):第一步,我们需要生成模式串的hashcode。生成hashcode的算法多种多样,好比:按位相加这是最简朴的方法,我们可以把a当做1,b当做2,c当做3......然后把字符串的所有字符相加,相加效果就是它的hashcode。bce = 2 + 3 + 5 = 10可是,这个算法虽然简朴,却很可能发生hash冲突,好比bce、bec、cbe的hashcode是一样的。

转换成26进制数既然字符串只包罗26个小写字母,那么我们可以把每一个字符串当成一个26进制数来盘算。bce = 2*(26^2) + 3*26 + 5 = 1435这样做的利益是大幅淘汰了hash冲突,缺点是盘算量较大,而且有可能泛起超出整型规模的情况,需要对盘算效果举行取模。为了利便演示,后续我们接纳的是按位相加的hash算法,所以bce的hashcode是10:第二步,生成主串当中第一个等宗子串的hashcode。

由于主勾通常要长于模式串,把整个主串转化成hashcode是没有意义的,只有比力主串当中和模式串等长的子串才有意义。因此,我们首先生成主串中第一个和模式串等长的子串hashcode,即abb = 1 + 2 + 2 = 5:第三步,比力两个hashcode。

yabo亚搏手机最新版app

显然,5!=10,说明模式串和第一个子串不匹配,我们继续下一轮比力。第四步,生成主串当中第二个等宗子串的hashcode。bbc = 2 + 2 + 3 = 7:第五步,比力两个hashcode。

显然,7!=10,说明模式串和第二个子串不匹配,我们继续下一轮比力。第六步,生成主串当中第三个等宗子串的hashcode。

bce= 2 + 3 + 5 = 10:第七步,比力两个hashcode。显然,10 ==10,两个hash值相等!这是否说明两个字符串也相等呢?别兴奋的太早,由于存在hash冲突的可能,我们还需要进一步验证。

第八步,逐个字符比力两字符串。hashcode的比力只是开端验证,之后我们还需要像BF算法那样,对两个字符串逐个字符比力,最终判断出两个字符串匹配。

最后得出结论,模式串bce是主串abbcefgh的子串,第一次泛起的下标是2。什么意思呢?让我们再来看一个例子:上图中,我已知子串abbcefg的hashcode是26,那么如何盘算下一个子串,也就是bbcefgd的hashcode呢?我们没有须要把子串的字符重新举行累加运算,而是可以接纳一个更简朴的方法。由于新子串的前面少了一个a,后面多了一个d,所以:新hashcode = 旧hashcode - 1 + 4 = 26-1+4 = 29 再下一个子串bcefgde的盘算也是同理:新hashcode = 旧hashcode - 2 + 5 = 29-2+5 = 32。


本文关键词:【,yabo,亚搏,手机,最新版,app,yabo亚搏手机最新版app,】,云,漫圈,什么

本文来源:yabo亚搏手机最新版app-www.gxkyym.com