2023年7月20日发(作者：)

字符串匹配算法详解为保证代码严谨性，⽂中所有代码均在 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输⼊: 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 数组之后，我们的 KMP 算法实现起来就很容易啦，另外我们看⼀下 next 数组到底是⼲什么⽤的。剩下的就不⽤说啦，完全⼀致啦，咱们将上⾯这个例⼦，翻译成和咱们开头对应的动画⼤家看⼀下。下⾯我们看⼀下代码，标有详细注释，⼤家认真看呀。注：很多教科书的 next 数组表⽰⽅式不⼀致，理解即可好啦好啦先就写这么多吧