字符串匹配算法详解

希望看到文章的你们,能够在今年的研究生考试中超常发挥。
愿你们都能考上自己心仪的学校,为你们的备考生涯划上一个完美的句号。做为你们的师兄有几句话想对你们说,希望这些话能对你们有一些帮助。
马上就要考试了,不要再继续啃难题了,看一些自己做过的题,曾经做错的题。因为我认为这个时候做难题,会比较打击自信心。考研的前一天我对自己十分有信心,但是不知道那天抽什么疯,做了一套特别难的数学模拟题,果不其然做的一塌糊涂,因为这套题让我怀疑自身实力,影响了考试心态。
不要放弃!无论考场上发生什么,也不要放弃,保持平常心,完成所有考试,当时我考外语的时候就感觉发挥极差,甚至有点不想去参加下面的考试,如果当时我没有参加剩下的考试,肯定就考不上了。所以一定一定要完成所有考试。
愿你们都能够成功上岸,你们真的很不容易,加油,必胜!另外咱们的文章视频中有送给你们的小彩蛋,大家快去看呀。

为保证代码严谨性,文中所有代码均在 leetcode 刷题网站 AC ,大家可以放心食用。

皇上生辰之际,举国同庆,袁记菜馆作为天下第一饭店,所以被选为这次庆典的菜品供应方,这次庆典对于袁记菜馆是一项前所未有的挑战,毕竟是第一次给皇上庆祝生辰,稍有不慎就是掉脑袋的大罪,整个袁记菜馆内都在紧张的布置着。此时突然有一个店小二慌慌张张跑到袁厨面前汇报,到底发生了什么事,让店小二如此慌张呢?

袁记菜馆内

店小二:不好了不好了,掌柜的,出大事了。

袁厨:发生什么事了,慢慢说,如此慌张,成何体统。(开店开久了,架子出来了哈)

店小二:皇上按照咱们菜单点了 666 道菜,但是咱们做西湖醋鱼的师傅请假回家结婚了,不知道皇上有没有点这道菜,如果点了这道菜,咱们做不出来,那咱们店可就完了啊。

(袁厨听了之后,吓得一屁股坐地上了,缓了半天说道)

袁厨:别说那么多了,快给我找找皇上点的菜里面,有没有这道菜!

找了很久,并且核对了很多遍,最后确认皇上没有点这道菜。菜馆内的人都松了一口气

通过上面的一个例子,让我们简单了解了字符串匹配,下面我们一起来详细了解一下吧。

字符串匹配:设 S 和 T 是给定的两个串,在主串 S 中找到模式串 T 的过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现的位置,否则匹配不成功,返回  -1。

例:

在上图中,我们试图找到模式串 T = baab,在主串 S = abcabaabcabac 中第一次出现的位置,即为红色阴影部分, T 第一次在 S 中出现的位置下标为 4 ( 字符串的首位下标是 0 ),所以返回 4。如果模式串 T 没有在主串 S 中出现,则返回 -1。

解决上面问题的算法我们称之为字符串匹配算法,今天我们来介绍三种字符串匹配算法,大家记得打卡呀,说不准面试的时候就问到啦。

BF算法(Brute Force)

这个算法很容易理解,就是我们将模式串和主串进行比较,一致时则继续比较下一字符,直到比较完整个模式串。不一致时则将模式串后移一位,重新从模式串的首位开始对比,重复刚才的步骤下面我们看下这个方法的动图解析,看完肯定一下就能搞懂啦。

通过上面的代码是不是一下就将这个算法搞懂啦,下面我们用这个算法来解决下面这个经典题目吧。

leetcdoe 28. 实现 strStr()

题目描述

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

示例 1:

输入: haystack = 'hello', needle = 'll' 输出: 2

示例 2:

输入: haystack = 'aaaaa', needle = 'bba' 输出: -1

题目解析

其实这个题目很容易理解,但是我们需要注意的是一下几点,比如我们的模式串为 0 时,应该返回什么,我们的模式串长度大于主串长度时,应该返回什么,也是我们需要注意的地方。下面我们来看一下题目代码吧。

题目代码

我们看一下BF算法的另一种算法(显示回退),其实原理一样,就是对代码进行了一下修改,只要看完咱们的动图,这个也能够一下就能看懂,大家可以结合下面代码中的注释和动图进行理解。

BM算法(Boyer-Moore)

我们刚才说过了 BF 算法,但是 BF 算法是有缺陷的,比如我们下面这种情况

如上图所示,如果我们利用 BF 算法,遇到不匹配字符时,每次右移一位模式串,再重新从头进行匹配,我们观察一下,我们的模式串 abcdex 中每个字符都不一样,但是我们第一次进行字符串匹配时,abcde 都匹配成功,到 x 时失败,又因为模式串每位都不相同,所以我们不需要再每次右移一位,再重新比较,我们可以直接跳过某些步骤。如下图

我们可以跳过其中某些步骤,直接到下面这个步骤。那我们是依据什么原则呢?

坏字符规则

我们之前的 BF 算法是从前往后进行比较 ,BM 算法是从后往前进行比较,我们来看一下具体过程,我们还是利用上面的例子。

BM 算法是从后往前进行比较,此时我们发现比较的第一个字符就不匹配,我们将主串这个字符称之为坏字符,也就是 f ,我们发现坏字符之后,模式串 T 中查找是否含有该字符 f,我们发现并不存在 f,此时我们只需将模式串右移到坏字符的后面一位即可。如下图

那我们在模式串中找到坏字符该怎么办呢?见下图

此时我们的坏字符为 f , 我们在模式串中,查找发现含有坏字符  f ,我们则需要移动模式串 T ,将模式串中的 f 和坏字符对齐。见下图。

然后我们继续从右往左进行比较,发现 d 为坏字符,则需要将模式串中的 d 和坏字符对齐。

那么我们在来思考一下这种情况,那就是模式串中含有多个坏字符怎么办呢?

那么我们为什么要让最靠右的对应元素与坏字符匹配呢?如果上面的例子我们没有按照这条规则看下会产生什么问题。

如果没有按照我们上述规则,则会漏掉我们的真正匹配。我们的主串中是含有 babac 的,但是却没有匹配成功,所以应该遵守最靠右的对应字符与坏字符相对的规则。

我们上面一共介绍了三种移动情况,分别是下方的模式串中没有发现与坏字符对应的字符,发现一个对应字符,发现两个。这三种情况我们分别移动不同的位数,那我们是根据依据什么来决定移动位数的呢?下面我们给图中的字符加上下标。见下图

下面我们来考虑一下这种情况。

此时这种情况肯定是不行的,不往右移动,甚至还有可能左移,那么我们有没有什么办法解决这个问题呢?继续往下看吧。

好后缀规则

好后缀其实也很容易理解,我们之前说过 BM 算法是从右往左进行比较,下面我们来看下面这个例子。

这里如果我们按照坏字符进行移动是不合理的,这时我们可以使用好后缀规则,那么什么是好后缀呢?

BM 算法是从右往左进行比较,发现坏字符的时候此时 cac  已经匹配成功,在红色阴影处发现坏字符。此时已经匹配成功的  cac 则为我们的好后缀,此时我们拿它在模式串中查找,如果找到了另一个和好后缀相匹配的串,那我们就将另一个和好后缀相匹配的串 ,滑到和好后缀对齐的位置。

是不是感觉有点拗口,没关系,我们看下图,红色代表坏字符,绿色代表好后缀

上面那种情况搞懂了,但是我们思考一下下面这种情况

上面我们说到了,如果在模式串的头部没有发现好后缀,发现好后缀的子串也可以。但是为什么要强调这个头部呢?

我们下面来看一下这种情况

但是当我们在头部发现好后缀的子串时,是什么情况呢?

下面我们通过动图来看一下某一例子的具体的执行过程

说到这里,坏字符和好后缀规则就算说完了,坏字符很容易理解,我们对好后缀总结一下

1.如果模式串含有好后缀,无论是中间还是头部可以按照规则进行移动。如果好后缀在模式串中出现多次,则以最右侧的好后缀为基准。

2.如果模式串头部含有好后缀子串则可以按照规则进行移动,中间部分含有好后缀子串则不可以。

3.如果在模式串尾部就出现不匹配的情况,即不存在好后缀时,则根据坏字符进行移动,这里有挺多文章没有提到,是个需要特别注意的地方,我是在这个论文里找到答案的,感兴趣的同学可以看下。

Boyer R S,Moore J S. A fast string searching algorithm[J]. Communications of the ACM,1977,10:762-772.

之前我们刚开始说坏字符的时候,是不是有可能会出现负值的情况,即往左移动的情况,所以我们为了解决这个问题,我们可以分别计算好后缀和坏字符往后滑动的位数(好后缀存在时),然后取两个数中最大的,作为模式串往后滑动的位数。

这破图画起来是真费劲啊。下面我们来看一下算法代码,代码有点长,我都标上了注释也在网站上 AC 了,如果各位感兴趣可以看一下,不感兴趣的话,理解坏字符和好后缀规则即可。可以直接跳到 KMP 部分

我们来理解一下我们代码中用到的两个数组,因为两个规则的移动位数,只与模式串有关,与主串无关,所以我们可以提前求出每种情况的移动情况,保存到数组中。

KMP算法(Knuth-Morris-Pratt)

我们刚才讲了 BM 算法,虽然不是特别容易理解,但是如果你用心看的话肯定可以看懂的,我们再来看一个新的算法,这个算法是考研时必考的算法。实际上 BM 和 KMP 算法的本质是一样的,你理解了 BM 再来理解 KMP 那就是分分钟的事啦。

我们先来看一个实例

注:为了让读者更容易理解,我们将指针移动改成了模式串移动,两者相对与主串的移动是一致的,重新比较时都是从指针位置继续比较。

通过上面的实例是不是很快就能理解 KMP 算法的思想了,我们继续往下看。

在上面的例子中我们提到了一个名词,最长公共前后缀,这个是什么意思呢?下面我们通过一个较简单的例子进行描述。

此时我们在红色阴影处匹配失败,绿色为匹配成功部分,则我们观察匹配成功的部分。

我们来看一下匹配成功部分的所有前后缀

我们的最长公共前后缀如下图,则我们需要这样移动

好啦,看完上面的图,KMP的核心原理已经基本搞定了,但是我们现在的问题是,我们应该怎么才能知道他的最长公共前后缀的长度是多少呢?怎么知道移动多少位呢?

刚才我们在 BM 中说到,我们移动位数跟主串无关,只跟模式串有关,跟我们的 bc,suffix,prefix 数组的值有关,我们通过这些数组就可以知道我们每次移动多少位啦,其实 KMP 也有一个数组,这个数组叫做 next 数组,那么这个 next 数组存的是什么呢?

next 数组存的咱们最长公共前后缀中,前缀的结尾字符下标。是不是感觉有点别扭,我们通过一个例子进行说明。

我们知道 next 数组之后,我们的 KMP 算法实现起来就很容易啦,另外我们看一下 next 数组到底是干什么用的。

剩下的就不用说啦,完全一致啦,咱们将上面这个例子,翻译成和咱们开头对应的动画大家看一下。

下面我们看一下代码,标有详细注释,大家认真看呀。

注:很多教科书的 next 数组表示方式不一致,理解即可

好啦好啦先就写这么多吧,累屁了,剩下的几种就先不写了,觉得这个文章对你有帮助的话,欢迎各位点赞,评论,在看,转发。哦,我还没评论功能。哈哈

(0)

相关推荐

  • 字符串硬核讲解

    字符串硬核讲解

  • 【原创】史上最透彻的KMP算法讲解

    【原创】史上最透彻的KMP算法讲解

  • 字符串匹配算法知多少?

    文章目录 BF算法 RK算法 编辑器中的全局替换方法:BM算法 坏字符 好后缀规则 代码实现 KMP算法 一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢? 想到是很正常的,谁 ...

  • Go 数据结构和算法篇(十二):字符串匹配之 KMP 算法

    昨天 以下文章来源于xueyuanjun ,作者xueyuanjun xueyuanjun学院君的订阅号,我会在这里持续更新优质全栈编程技术教程,包括但不限于 Golang.PHP.JavaScrip ...

  • RealPython 基础教程:Python 字符串用法详解

    字符串是一个由字符数据组成的序列.字符串处理是编程必备的技能,很少有应用程序不需要操作字符串的. Python 提供了丰富的运算符.函数和类方法来操作字符串. 通过本文,你将了解如何访问字符串以及提取 ...

  • python 通关字符串操作方法详解-大量案例

    给IT入门加星标,提升编程技能 IT入门(ID:learncode)整理  原作者:战争热诚 字符串序列用于表示和存储文本,python中字符串是不可变对象.字符串是一个有序的字符的集合,用于存储和表 ...

  • (正则表达式)linux shell 字符串操作(长度,查找,替换,匹配)详解

    在做shell批处理程序时候,经常会涉及到字符串相关操作.有很多命令语句,如:awk,sed都可以做字符串各种操作. 其实shell内置一系列操作符号,可以达到类似效果,大家知道,使用内部操作符会省略 ...

  • 《Java 底层原理》String字符串详解

    前言 Java 字符串底层是如何存储的,如何提高性能的,今天就来好好了解一下. 字符串的存储结构 Jvm 有专门的字符串常量池用于存放字符串,存放字符串的数据结构是HashTable. HashTab ...

  • Shell if、for、while流程语句以及整数字符串判断比较的实例详解

    前言: 实际上Shell是一个命令解释器,它解释由用户输入的命令并且把它们送到内核.不仅如此,Shell有自己的编程语言用于对命令的编辑,它允许用户编写由shell命令组成的程序.Shell编程语言具 ...

  • C string字符串比较方法详解

    字符串可以和类型相同的字符串相比较,也可以和具有同样字符类型的数组比较. Basic_string 类模板既提供了  >.<.==.>=.<=.!= 等比较运算符,还提供了 c ...

  • Java字符串详解

    字符串即字符的组合,在Java中,字符串是一个类,所以我们见到的字符串都是对象. 常见创建字符串手段: 每当有一个字面值出现的时候,JVM虚拟机就会创建一个字符串 调用String的构造方法创建一个字 ...

  • 胎元命宫详解

    胎元命宫详解 胎元命宫 8.1 胎元 胎, 指人受精怀胎的月份. 其起法是: 人生月后紧接着这个月的天干与生月后第三个月的地支相配, 就为胎元. 如1998年八月生人, 八月为辛酉, 辛后一干是壬, ...

  • 批八字算婚姻详解

    批八字算婚姻详解 很多人喜欢在孩子一出生的时候就给他们算一下八字,因为他们相信孩子的八字和命运是相对注定了的,通过算命之后可以顺利的避免一些可能在生活中遇到的一些问题和坎坷,也可以顺利度过一些&quo ...